Изменения

Будем рассматривать запрос на примере задачи RSQ''Замечание.''Используем в алгоритме не отрезки, а полуинтервалы (запрос суммылевая граница включительно, а правая {{---}} нет)[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]

Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков ]] и задача найти сумму идет запрос на отрезке полуинтервале <tex>[a .. \ldots b])</tex>, далее искомый.

Запустим рекурсивную процедуру от всего отрезкаВ качестве параметров рекурсий передаем следующие переменные:* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.

*если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.''Например''Для текущего состояния проверяем следующие условия:

* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.:''Например'': текущий <tex>[1..2]\ldots 3)</tex>, а искомый <tex>[3 .. 4]\ldots 5)</tex>;

*Если текущий отрезок совпадаетполуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.:''Например'':текущий <tex>[2 \ldots 3)</tex>, а искомый <tex>[2 \ldots 4)</tex>;

текущий и искомый <tex>[2* Иначе переходим к рекурсивным вызовам функций от детей вершины.При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.3]</tex>;

Далее переходим к рекурсивным вызовамрезультат функции от текущего отрезка и искомого = сумма результатов от детей текущего отрезка и искомогоТак как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.

Рассмотрим работу программы данный алгоритм на дереве отрезков для элементов примере задачи <tex>[1 \mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на отрезке). При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.  Пусть дерево содержит <tex>8]</tex>.Пусть листьев и запрашиваемая сумма {{--- }} это отрезок <tex>[2 1 \ldots 4]</tex> (полуинтервал <tex>[1 \ldots 5)</tex>).[[Файл:Image_4. 5png|right|602px|Пример рабoты алгоритма]]Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня): * На глубине <tex>0</tex>.** Текущий полуинтервал <tex>[0 \ldots 8)</tex> пересекается с <tex>[1 \ldots 5) \Rightarrow</tex> рекурсивно переходим к <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex>

*лист 6 не пересекается с отрезком Таким образом ответ на полуинтервале <tex>[2 .. 1 \ldots 5])</tex> =равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2)</tex> возвращаем нулевое значение, лист 5 целиков внутри <tex>[2 .. 5]\ldots 4)</tex> =и <tex> возвращаем значение в листе [4 \ldots 5)</tex>.

Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией. Пусть в узлах дерева хранятся структуры из трех полей:* <codetex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.  '''int''' query('''int''' node, '''int''' a, '''int''' b) l = tree[node].left r = tree[node].right '''if''' [l, r) <tex>\cap </tex> [a, b) == <tex>\varnothing</tex> '''return''' ''<tex>\varepsilon</tex>'' <span style="color:#008000">// <tex>\varepsilon</tex> {{---}} нейтральный для данной операции элемент</span> '''if''' [l, r) <tex>\subset</tex> [a, b) '''return''' tree[node].res '''return''' query(node * 2 + 1, a, b) <tex> \circ </tex> query(node * 2 + 2, a, b)

int sum (int v, int tl, int tr, int l, int r)==См. также== { if (* [[l,rРеализация запроса в дереве отрезков снизу] <tex>\bigcap</tex> [tl, tr]) = return 0; if (* [l,r] = [tl, trДерево отрезков. Построение]) return t[v]; int tm = (tl + tr) / 2; return sum (v*2, tl, tm, l, min(r,tm)) + sum (v*2+1, tm+1, tr, max(l,tm+1), r); } </code>

==СсылкиИсточники информации==* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия — Дерево отрезков]

* [http://e-maxxrain.ifmo.ru/algocat/segment_tree view.php/vis/trees/segment- MAXimal :: algo :2006 Дискретная математика: Дерево Алгоритмы — Визуализатор дерева отрезков]

[http[Категория: Дискретная математика и алгоритмы]][[Категория://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 - Дерево отрезков — Википедия]]