Изменения

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

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

Будем передавать в качестве параметров рекурсий следующие переменные:* <tex>node</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>O(\log n)</tex> отрезков (поскольку на каждом уровне дерева рекурсия может быть дойти до не более , чем двух отрезков из разбиениявершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex> ), то данная реализация операция выполняется за <tex>O(\log n)</tex>.

Рассмотрим работу программы данный алгоритм на дереве отрезков для элементов примере задачи <tex>[1 .. 8]\mathrm{RSQ}</tex>.Пусть запрашиваемая сумма (Range Sum Query {{- это отрезок <tex>[2 .. 5]</tex>--}} запрос суммы на отрезке).

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

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

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

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

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