Многомерное дерево отрезков

Дерево отрезков можно обобщить в многомерный случай.

Пусть задано [math]p[/math]-мерное пространство с координатными осями [math]x_1, x_2...x_p[/math].При построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по [math]x_1 [/math], затем по [math]x_2[/math] и т.д

Анализ и оценка структуры

Структура использует [math]O(n^p[/math] памяти, и отвечает на запрос за [math]O(log^{p} n)[/math], где [math]p[/math]-размерность дерева.