Изменения

Будем рассматривать запрос на примере задачи 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 .. 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>.

Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией. Пусть в узлах дерева хранятся структуры из трех полей:* <codetex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.

'''int sum ''' query('''int v''' node, '''int tl, int tr''' a, '''int ''' b) l, int = tree[node].left r)= tree[node].right { '''if (''' [l,r] ) <tex>\bigcapcap </tex> [tla, tr]b) = = <tex>\varnothing</tex> '''return 0;''' ''<tex>\varepsilon</tex>'' <span style="color:#008000">// <tex>\varepsilon</tex> {{---}} нейтральный для данной операции элемент</span> '''if (''' [l,r] = ) <tex>\subset</tex> [tla, tr]b) '''return t''' tree[vnode];.res int tm = (tl + tr) / 2; '''return sum ''' query(vnode *2+ 1, tl, tm, la, min(r,tmb)) + sum <tex> \circ </tex> query(vnode *2+12, tm+1a, tr, max(l,tm+1), rb); } </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://rain.ifmo.ru/cat/view.wikipedia.orgphp/vis/wikitrees/%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 segment- Дерево 2006 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков — Википедия]