Изменения

==Описание==Данная рекурсивная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.

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

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

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

* Если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.''Например''Для текущего состояния проверяем следующие условия: текущий <tex>[1..2]</tex>, а искомый <tex>[3 .. 4]</tex>;

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

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

int sum (int v, int tl, int tr, int l, int r)Пусть в узлах дерева хранятся структуры из трех полей: { if ([l,r] * <tex>\bigcapmathtt{left}</tex> [tl{{---}} левая граница полуинтервала, tr]) = за который "отвечает" текущая вершина. return 0; if ([l,r] = [tl, tr]) return t[v]; int tm = (tl + tr) * <tex>\mathtt{right}</ 2;tex> {{---}} правая граница этого полуинтервала. return sum (v*2, tl, tm, l, min(r,tm)) + sum (v*2+1, tm+1, tr, max(l,tm+1), r); <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 - Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]