97
правок
Изменения
Нет описания правки
[[Дерево отрезков. Построение|Дерево отрезков]] можно обобщить в многомерный случай для решения таких задач, как поиск суммы на прямоугольнике(или гиперпрямоугольной области).
{{Задача
|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>p = 2</tex>.
Пусть задан массив элементов размера <tex>n \times m</tex>.Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате <tex>y</tex>, которые находятся на том же отрезке.
К примеру,двумерное дерево размером <tex>4 \times 4 :</tex>
Структура использует <tex>O(n^p)</tex> памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева.
Ответ на запрос в таком дереве будет производиться так же,как и построение: сначала по координате <tex>x_1</tex>, затем, когда дошли до какой-либо вершины по первой координате, вызвать запрос от этого же дерева по <tex>x_2</tex> и так далее.Получается, что для <tex>n-</tex>мерного дерева запрос выполняется за <tex>O(log (s_{x_1})* \cdot log (s_{x_2})...log (s_{x_n}))</tex> (для рассмотренного двумерного дерева будет <tex>log (n) * \cdot log (m) </tex> )
==Источники==
*e-maxx.ru: [http://e-maxx.ru/algo/segment_tree Дерево отрезков] <br/>*F. P. Preparata, M.I. Shamos - Вычислительная геометрия [http://pogorskiy.narod.ru/rectq.htm Главы о региональном поиске]
==См. также==
*[[Дерево отрезков. Построение]] <br/>*[[Сжатое многомерное дерево отрезков]] <br/>*[[Многомерное дерево Фенвика]] <br/>
