Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] естественным образом обобщается на двумерный и вообще говоря многомерный случай. Такая структура данных может вычислять значение некоторой [[Ассоциативная_операция|ассоциативной функции]] на гиперпрямоугольнике за . Например, она позволяет решать следующую задачу. Дан <tex>O(\log^{p} n)</tex>-мерный массив, где индекс каждого измерения массива может принимать значения от 1 до <tex>pn</tex> {{---}} размерность пространства. Необходимо уметь изменять значение элемента массива, а также находить сумму на <tex>np</tex> -мерной области. Каждую из этих операций многомерное дерево отрезков выполняет за <tex>O(\log^{{---p}} ширина гиперкуба на котором производятся вычисленияn)</tex>.

==СтруктураПринцип работы==<tex>n</tex>-мерное дерево отрезков {{---}} обычное дерево отрезков, элементами которого являются деревья отрезков размерности на 1 меньше. Основная идея заключается в рекурсивном переходе к деревьям меньшей размерности. Рассмотрим работу этого принципа на следующем примере. Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...x_p</tex>. Необходимо вычислять некоторую ассоциативную функцию найти значение некоторой ассоциативной функции на гиперпрямоугольнике. Для этого сначала найдем элементы дереваФункция, вычисляющая ответ, должна работать следующим образом. На вход она принимает <tex>i</tex>-мерное дерево отрезков, которое соответствует рассматриваемой области (где <tex>i</tex> {{---}} количество координатных осей, которые не были рассмотрены), соответствующие а также <tex>x_1i</tex> координате-мерную область, для которой следует вычислить функцию. Для каждого из этих элементов рекурсивно перейдем в соответствующие им Вначале она находит <tex>i-1</tex>-мерные деревья отрезков и в них найдем элементы, отвечающие соответствующим координатам которые соответствуют отрезку по <tex>x_2p-i+1</tex> исходной гиперпрямоугольной областикоординате, и рекурсивно запускается от них (если текущее дерево одномерное, то функция просто возвращает ответ из соответствующего листа). После этого считает итоговый результат, используя полученные после рекурсивных вызовов значения. Для того, чтобы определить, от каких именно деревьев отрезков следует запускаться рекурсивно, действовать необходимо так же, как и тв одномерном случае. Т. де. если текущий отрезок не пересекается с необходимым, то возвращаем нейтральный элемент, если он полностью лежит в необходимом отрезке, то рекурсивно переходим к следующей размерности, иначе разобьем текущий отрезок пополам, и рассмотри отдельно каждую из частей. Таким образом, алгоритм совершит <tex>p</tex> вхождений в рекурсию, каждая итерация которой работает за <tex>O(\log n)</tex> и получим необходимую асимптотику.