1632
правки
Изменения
м
rollbackEdits.php mass rollback
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. \ldots b)</tex>.
В качестве параметров рекурсий передаем следующие переменные:
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
Для текущего состояния проверяем следующие условия :
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
:''Например'': текущий <tex>[1..\ldots 3)</tex>, а искомый <tex>[3 .. \ldots 5)</tex>;
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
:''Например'': текущий <tex>[2..\ldots 3)</tex>, а искомый <tex>[2..\ldots 4)</tex>;
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
==Пример==
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ }</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
{{---}} это отрезок <tex>[1 .. \ldots 4]</tex> (полуинтервал <tex>[1 .. \ldots 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>[4 .. \ldots 8)</tex>
* На глубине <tex>1</tex>.
** <tex>[0 .. \ldots 4)</tex> и <tex>[4 .. \ldots 8)</tex> пересекаются с <tex> [1 .. \ldots 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..\ldots 2)</tex>, <tex>[2 .. \ldots 4)</tex>, <tex>[4 .. \ldots 6)</tex> и <tex>[6 .. \ldots 8)</tex>
* На глубине <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>[1 .. \ldots 5) \Rightarrow </tex> возвращаем нулевое значение
* На глубине <tex>3</tex>.
** Листья <tex>[1 .. \ldots 2), [4 .. \ldots 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них** Листья <tex>[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>.
==Реализация==
Пусть в узлах дерева хранятся структуры из трех полей:
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.
'''int''' query('''int''' node, '''int''' a, '''int''' b)
