333
правки
Изменения
→Пример
==Пример==
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).
[[Файл:Image_2.png|right|Пример работы алгоритма]]
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):
*На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5)</tex>, то переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex>.
*На глубине 2. <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex>; <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке; а <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение.
* На глубине 3. Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них, в то время как листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение.
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.
