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

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

Построение

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

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

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