==Принцип работы==
[[Файл:SegmentTreeWorking.png|thumb|450px|right|Пример некоторой стадии работы алгоритма (поиск элементов, подходящих некоторой области)]]
<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на 1 меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...x_p</tex>. Необходимо найти значение некоторой ассоциативной функции на гиперпрямоугольнике. Функция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), а также <tex>i</tex>-мерную область, для которой следует вычислить функцию. Вначале она находит <tex>i-1</tex>-мерные деревья отрезков, которые соответствуют отрезку по <tex>p-i+1</tex> координате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения. Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и в одномерном случае. Т. е. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей размерности, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей. Таким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.
==Двумерное дерево отрезков==Рассмотрим следующую задачу.На рисунке справа показан пример обработки очередной координаты (поиск соответствующих отрезку элементов {{Задача|definition=Дано поле размером <tex>N \times M</tex>, заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов: * Изменить некоторый элемент* Посчитать значение некоторой ассоциативной функции <tex>\times</tex> на прямоугольной области---}}деревьев на 1 меньшей мерности).
==Хранение==
[[Файл:SegmentTree2DExample.png|thumb|250px|right|Пример двумерного дерева отрезков для 16 элементов]]
Двумерное Пусть необходимо хранить дерево отрезков для <tex>p</tex>-мерной области, размеры которой <tex>n_1 \times n_2 \times ... \times n_p</tex>. Удобнее всего это делать с помощью <tex>p</tex>-мерного массива. Однако его размеры по каждой координате, так же как и в одномерном случае, должны превышать размеры соответствующего отрезка в 4 раза. Т. е. потребуется массив размером <tex>4 n_1 \times 4 n_2 \times ... \times 4 n_p</tex>. Так двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</tex>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
На рисунке справа показан пример дерева отрезков для суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</tex> хранится сумма всех элементов.
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</tex> {{---}} общее количество элементов.
==Псевдокод для двумерного случая==
Построение:
// first call - buildX(0, 0, n, a, t)
// a - исходный массив
// t - массив дерева отрезков
// [leftX, rightX) - полуинтервал
buildX(vertexX, leftX, rightX, a[][], t[][])
if leftX != rightX
mx = (leftX + rightX + 1) / 2
buildX(vertexX * 2 + 1, leftX, mx, a, t)
buildX(vertexX * 2 + 2, mx, rightX, a, t)
buildY(vertexX, leftX, rightX, 0, 0, m, a, t)
buildY(vertexX, leftX, rightX, vertexY, leftY, rightY, a[][], t[][])
if leftY == rightY
if leftX == rightX
t[vertexX][vertexY] = a[leftX][leftY]
else
t[vertexX][vertexY] = t[vertexX * 2 + 1][vertexY] <tex>\times</tex> t[vertexX * 2 + 2][vertexY]
else
my = (leftY + rightY + 1) / 2
buildY(vertexX, leftX, rightX, vertexY * 2 + 1, leftY, my, a, t)
buildY(vertexX, leftX, rightX, vertexY * 2 + 2, my, rightY, a, t)
t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\times</tex> t[vertexX][vertexY * 2 + 2]
Подсчет некоторой функции от элементов, лежащих в прямоугольной области:
// first call - operationX(0, 0, n - 1, leftX, rightX, leftY, rightY, t)
operationX(vertexX, leftX, rightX, needLeftX, needRightX, needLeftY, needRightY, t[][])
if needLeftX > needRightX
return 0
if leftX == needLeftX && rightX == needRightX
return operationY(vertexX, 0, 0, m - 1, needLeftY, needRightY)
med = (leftX + rightX) / 2
return operationX(vertexX * 2 + 1, leftX, med, leftX, min(needRightX, med), needLeftY, needRightY, t) <tex>\times</tex>
operationX(vertexX * 2 + 2, med + 1, rightX, max(needLeftX, med + 1), needRightX, needLeftY, needRightY, t)
operationY(vertexX, vertexY, leftY, rightY, needLeftY, needRightY)
if needLeftY > needRightY
return 0
if leftY == needLeftY && rightY == needRightY
return t[vertexX][vertexY]
med = (leftY + rightY) / 2
return operationY(vertexX, vertexY * 2 + 1, leftY, med, needLeftY, min(needRightY, med), t) <tex>\times</tex>
operationY(vertexX, vertexY * 2 + 2, med + 1, rightY, max(needLeftY, med + 1), needRightY, t)
Обновление элемента:
// first call - updateX(0, 0, n - 1, x, y, val, t)
updateX(vertexX, leftX, rightX, x, y, val, t[][])
if leftX != rightX
mx = (leftX + rightX) / 2
if x <= mx
updateX(vertexX * 2 + 1, leftX, mx, x, y, val, t)
else
updateX(vertexX * 2 + 2, mx + 1, rightX, x, y, val, t)
updateY(vertexX, leftX, rightX, 0, 0, m - 1, x, y, val, t)
updateY(vertexX, leftX, rightX, vertexY, leftY, rightY, x, y, val, t[][])
if leftY == rightY
if leftX == rightX
t[vertexX][vertexY] = val
else
t[vertexX][vertexY] = t[vertexX * 2 + 1][vertexY] <tex>\times</tex> t[vertexX * 2 + 2][vertexY]
else
my = (leftY + rightY) / 2
if y <= my
updateY(vertexX, leftX, rightX, vertexY * 2 + 1, leftY, my, x, y, val, t)
else
updateY(vertexX, leftX, rightX, vertexY * 2 + 2, my + 1, rightY, x, y, val, t)
t[vertexX][vertexY] = t[vertexX][vertexY * 2 + 1] <tex>\times</tex> t[vertexX][vertexY * 2 + 2]
==Многомерный случай==
