Изменения

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

Строится такое дерево за линейное время.Структура использует <tex>O(n^p)</tex> памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева. Ответ на запрос в таком дереве будет производиться так же,как и построение: сначала по координате <tex>x_1</tex>, затем <tex>x_2</tex> и так далее.