Изменения

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

==Пример==Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке), то есть пусть Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] построенное дерево отрезков и задача найти сумму идет запрос на отрезке полуинтервале <tex>[a \ldots b)</tex>. В качестве параметров рекурсий передаем следующие переменные:* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева. * <tex>a</tex>, <tex>b]</tex> {{---}} левая и правая границы запрашиваемого полуинтервала. Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.[[ФайлЗапустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины). Для текущего состояния проверяем следующие условия:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]

Будем передавать в качестве параметров рекурсий следующие переменные:* <tex>node</tex> {{---}} номер(в массиве Если текущий полуинтервал не пересекается с деревом отрезков) текущей вершины дерева.* <tex>l</tex>искомым, <tex>r</tex> {{---}} левая и правая границы отрезков, за которые "отвечает" наша вершинато возвращаем нейтральный элемент.* :''Например'': текущий <tex>a[1 \ldots 3)</tex>, а искомый <tex>b[3 \ldots 5)</tex> {{---}} левая и правая границы запрашиваемого отрезка.;

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

* Если текущий Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок не пересекается с искомым, то возвращаем нулевое значение.''Например'': текущий за который отвечает вершина предыдущего уровня), а всего уровней <tex>[1..2]\log n</tex>, а искомый то операция выполняется за <tex>[3 .. 4]O(\log n)</tex>;.

* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом сумма Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на текущем отрезке равна сумме результатов функций, запущенных от детей). ''Замечание:''

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

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

* На глубине <tex>0</tex>. ** Текущий полуинтервал <tex>[0 \ldots 8)</tex> пересекается с <tex>[1 \ldots 5) \Rightarrow</tex> рекурсивно переходим к <tex>[0 \ldots 4)</tex> и <tex>[Файл:Шагал1538.JPG|right|380px|thumb|Дерево отрезков]]4 \ldots 8)</tex>

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

*На глубине <tex>[1 .. 4]2</tex> выходит за границы. ** <tex> [0 \ldots 2 .. 5])</tex>, и <tex>[5 .. 8]4 \ldots 6)</tex> выходит за границы пересекаются с <tex>[2 .. 1 \ldots 5]) \Rightarrow </tex> => переходим по рекурсивным вызовам на в листья <tex>[0 \ldots 1 .. ), [1 \ldots 2]), [4 \ldots 5), [5 \ldots 6) </tex>, ** <tex>[3 .. 2 \ldots 4]) </tex> и полностью лежит внутри <tex>[1 \ldots 5 .. ) \Rightarrow </tex> возвращаем сумму на этом отрезке** <tex>[6]\ldots 8)</tex>, не пересекается с <tex>[7 .. 8]1 \ldots 5) \Rightarrow </tex>.возвращаем нулевое значение

*На глубине <tex>[1 .. 2]3</tex> выходит за границы . ** Листья <tex>[1 \ldots 2 .. 5]</tex> => переходим в листья 1), 2; <tex>[3 .. 4]\ldots 5)</tex> целиком внутри лежат в запрашиваемом интервале <tex>[2 .. 5]\Rightarrow </tex> => возвращаем значение значения в них** Листья <tex>[3 .. 4]</tex>; <tex>[7 .. 8]</tex> не пересекается с <tex>[2 .. 5]</tex> => возвращаем нулевое значение0 \ldots 1), <tex>[5 .. \ldots 6])</tex> выходит за границы лежат вне <tex>[2 .. 1 \ldots 5]</tex> => переходим к листьям <tex>5</tex> и <tex>6) \Rightarrow </tex>возвращаем нейтральное значение

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

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

int get_sum (int node, int a, int b)Пусть в узлах дерева хранятся структуры из трех полей: { l = tree[node].left; r = tree[node].right; // [l, r) 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 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]