Изменения

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

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

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

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

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

Так как каждый отрезок полуинтервал разбивается не более, чем на <tex>O(\log n)</tex> отрезков полуинтервал (поскольку на каждом уровне дерева может быть не более двух отрезков полуинтервалов из разбиения, а всего уровней <tex>\log n</tex> ), то данная реализация выполняется за <tex>O(\log n)</tex>.

'''Например''' рассмотрим ==Пример==Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке). Рассмотрим работу программы алгоритма для вычисления суммы на дереве отрезков для элементов отрезке. Пусть дерево содержит 8 листьев и запрашиваемая сумма - это отрезок <tex>[1 .. 84]</tex>.Пусть запрашиваемая сумма - это отрезок ( полуинтервал <tex>[2 1 .. 5])</tex>.)

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

*<tex>[1 0 .. 4])</tex> выходит за границы<tex> [2 1 .. 5])</tex>, <tex>[5 4 .. 8])</tex> выходит за границы <tex>[2 1 .. 5])</tex> => переходим по рекурсивным вызовам на <tex>[1 0 .. 2])</tex>, <tex>[3 2 .. 4])</tex> и <tex>[5 4 .. 6])</tex>, <tex>[7 6 .. 8])</tex>.

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

*лист листья <tex>65</tex> и <tex>0</tex> не пересекается с отрезком полуинтервалом <tex>[2 1 .. 5])</tex> => возвращаем нулевое значение, лист листья <tex>4</tex>5и <tex>1</tex> целиков внутри <tex>[2 1 .. 5])</tex> => возвращаем значение значения в листе <tex>5</tex>этих листьях.