Многомерное дерево отрезков

Дерево отрезков можно обобщить в многомерный случай для решения таких задач, как поиск суммы на прямоугольнике(или гиперпрямоугольной области).

Задача:

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

Построение

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

Пример задачи, в которой удобно использовать многомерное дерево отрезков

Пример двумерного дерева

Рассмотрим процесс построения предельного случая при [math]p = 2[/math]. Пусть задан массив элементов размера [math]n \times m[/math].Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате [math]y[/math], которые находятся на том же отрезке.

К примеру,двумерное дерево размером [math]4 \times 4 :[/math]

Анализ и оценка структуры

Строится такое дерево за линейное время. Структура использует [math]O(n^p)[/math] памяти, и отвечает на запрос за [math]O(log^{p} n)[/math], где [math]p[/math]-размерность дерева.

Ответ на запрос в таком дереве будет производиться так же,как и построение: сначала по координате [math]x_1[/math], затем, когда дошли до какой-либо вершины по первой координате, вызвать запрос от этого же дерева по [math]x_2[/math] и так далее.Получается, что для [math]n-[/math]мерного дерева запрос выполняется за [math]O(log (s_{x_1})* log (s_{x_2})...log (s_{x_n})[/math] (для рассмотренного двумерного дерева будет [math]log (n) * log (m) [/math] )

Источники

e-maxx.ru: Дерево отрезков
F. P. Preparata, M.I. Shamos - Вычислительная геометрия Главы о региональном поиске

См. также

Дерево отрезков. Построение
Сжатое многомерное дерево отрезков
Многомерное дерево Фенвика