Изменения
→Принцип работы
==Принцип работы==
[[Файл:SegmentTreeWorking.png|thumb|600px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]
<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на единицу меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...\ldots x_p</tex>. Необходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике.
Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>i</tex>-мерную область, для которой следует вычислить функцию. Вначале она находит <tex>i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>p-i+1</tex> координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения.
