Изменения

{{Задача

|definition=

Рассматривается задача регионального поиска. Задано множество точек в <tex>p-</tex>мерном евклидовом пространстве. Образцом для поиска является гиперпрямоугольная область.Найти сумму/минимум/максимум.

}}

==Построение==

Пусть задано <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>x_1</tex>, затем, когда дошли до какой-либо вершины по первой координате, вызвать запрос от этого же дерева по <tex>x_2</tex> и так далее.Получается, что для <tex>n-</tex>мерного дерева запрос выполняется за <tex>O(log (s_{x_1})* log (s_{x_2})...log (s_{x_n})</tex> (для рассмотренного двумерного дерева будет <tex>log (n) * log (m) </tex> )