144
правки
Изменения
Нет описания правки
Дерево отрезков можно обобщить в многомерный случайдля решения таких задач, как поиск суммы на прямоугольнике(или гиперпрямоугольной области).
{{Задача
|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>
[[Файл:Многомерное до.jpg]]
Структура использует <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})* log (s_{x_2})...log (s_{x_n})</tex> (для рассмотренного двумерного дерева будет <tex>log (n) * log (m) </tex> )
