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