228
правок
Изменения
→Алгоритм
[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]
Пусть есть дерево отрезков и задача найти сумму на отрезке <tex>[a .. b]</tex>, далее искомый.
Запустим рекурсивную процедуру от всего отрезка.
Например:
текущий <tex>[1..2]</tex>, а искомый <tex>[3 .. 4]</tex>;
*текущий отрезок целиком внутри, то возвращаем значение в вершине.
Например:
текущий <tex>[2..3]</tex>, а искомый <tex>[1 .. 4]</tex>;
Далее переходим к рекурсивным вызовам
