Изменения

Будем рассматривать запрос Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммына отрезке), то есть пусть есть уже построенное дерево отрезков и задача найти сумму на отрезке <tex>[a .. b]</tex>.

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

Запустим рекурсивную процедуру от всего отрезка(то есть от корневой вершины).

Проверять будем два Для текущего состояния проверяем следующие условия :

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

* Текущий отрезок совпадает, то возвращаем значение в текущей вершине.''Например'': текущий и искомый <tex>[12..2]</tex>, а искомый <tex>[3 .. 4]</tex>;

*текущий отрезок совпадает, то возвращаем значение в вершине.''Например'': текущий и искомый <tex>[2..3]</tex>; Далее Иначе переходим к рекурсивным вызовамрезультат функции функций от текущего отрезка и искомого = детей вершины. При этом сумма на текущем отрезке равна сумме результатов функций, запущенных от детей текущего отрезка и искомого.