Многомерное дерево отрезков — различия между версиями
Строка 5: | Строка 5: | ||
==Пример двумерного дерева== | ==Пример двумерного дерева== | ||
− | + | Рассмотрим процесс построения предельного случая при <tex>p = 2</tex>. | |
+ | Пусть задан массив элементов размера <tex>n \times m</tex>.Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате <tex>y</tex>, которые находятся на том же отрезке. | ||
==Анализ и оценка структуры== | ==Анализ и оценка структуры== | ||
Структура использует <tex>O(n^p</tex> памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева. | Структура использует <tex>O(n^p</tex> памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева. |
Версия 06:02, 15 июня 2011
Дерево отрезков можно обобщить в многомерный случай.
Построение
Пусть задано
-мерное пространство с координатными осями .Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по , затем по и так далее...Далее дерево строится рекурсивно: далее координаты по обрабатываем по координатам , ,то есть по всем возможным и далее по аналогии...То есть получается, что основная идея построения многомерного дерева отрезков - вкладывание деревьев отрезка друг в друга.Пример двумерного дерева
Рассмотрим процесс построения предельного случая при
. Пусть задан массив элементов размера .Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате , которые находятся на том же отрезке.Анализ и оценка структуры
Структура использует
памяти, и отвечает на запрос за , где -размерность дерева.