Изменения

==Алгоритм==

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

[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]

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

[[Файл:Шагал1538.JPG|right|380px|thumb|Дерево отрезков]]

Пусть запрашиваемая сумма - это отрезок <tex>[2 .. 5]</tex>.