Изменения

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