Изменения

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

Будем передавать в качестве параметров рекурсий следующие переменные:* <tex>node</tex> {{---}} номер(в массиве с деревом Пусть есть уже [[Дерево отрезков) текущей вершины дерева.* Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a</tex>, <tex>\ldots b)</tex> {{---}} левая и правая границы запрашиваемого отрезка.

Пусть В качестве параметров рекурсий передаем следующие переменные:* <tex>lnode</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.* <tex>a</tex>, <tex>rb</tex> {{---}} это левая и правая границы отрезков, за которые "отвечает" наша вершина, причем левые границы обоих отрезков - включительно, а правые - нет. В дальнейшем будем называть подобную структуру полуинтверваломзапрашиваемого полуинтервала.

Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.Запустим рекурсивную процедуру от всего отрезкаполуинтервала (то есть от корневой вершины).

Для текущего состояния проверяем следующие условия :

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

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

* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом в зависимости от типа запроса возвращаем значение на текущем отрезкеполуинтервале, как некоторую функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.''Замечание:''

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

==Пример==Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке). При этом сумма на текущем отрезке полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операций операции на этих детях.

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

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

Рассмотрим реализацию задачи RSQо дереве отрезков с произвольной ассоциативной бинарной операцией.<code>

int get_sum (int node, int a, int b) { // Используем Пусть в реализаций полуинтервалы узлах дерева хранятся структуры из трех полей: l = tree[node].left; r = tree[node].right; if [l, r) * <tex>\bigcapmathtt{left}</tex> [a{{---}} левая граница полуинтервала, b) == за который "отвечает" текущая вершина.* <tex> \varnothingmathtt{right}</tex>{{---}} правая граница этого полуинтервала. return 0; if [l, r) == [a, b) return tree[node]; int m = (l + r) / 2; return get_sum (node * 2 + 1, a, min(b, m)) + get_sum (node * 2 + 2, max(a, m), b); <tex> \mathtt{res} </codetex>{{---}} результат операции на полуинтервале.

'''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)

==См. также==* [[Реализация запроса в дереве отрезков снизу]]* [[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков. Построение]]

==Источники информации==* [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://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]