54
правки
Изменения
Нет описания правки
{{notready}}
Рассмотрим задачу хранения множества точек Nd-мерного пространства с возможностью перечисления точек, содержащихся в Nd-мерном прямоугольнике запроса. Эту задачу решает range-tree.
== Постановка задачи ==
Пусть дано пространство <math>X</math>, являющееся произведением <math>Nd</math> линейных порядков:<math>X = X_1 \times X_2 \times \hdots \times X_NX_d</math>.
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots X_NX_d</math>:<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_Na_d, b_Nb_d]</math>, где <math>a_i, b_i \in X_i</math>.
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
== Одномерный случай ==
Для начала рассмотрим задачу в случае <math>N d = 1</math>.
Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
* <math>Nd</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>Nd-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots \times X_NX_d</math>) для множества элементов, являющихся листами поддерева этой вершины.
Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:
Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.
== Оценка времени работы и потребляемой памяти ==
Фаза алгоритма, обрабатывающая одну координату, может выдать <math>O(\log n)</math> поддеревьев высотой <math>O(\log n)</math>, каждое из которых будет обработано фазой по следующей координате, и т.д. Таким образом, время запроса - <math>O(\log^d n + k)</math>, где k - размер ответа (количество точек ответа).
Докажем по индукции оценку в <math>O(n \log^{d-1} n)</math> для потребляемой памяти для структуры range-tree.
<math>d = 1</math>: в одномерном случае range-tree является обычным деревом, оценка в <math>O(n \log^0 n) = O(n)</math> очевидна.
<math>d > 1</math>: очевидно, что основным слагаемым в оценке потребляемой памяти будут не сами хранимые элементы, а range-tree меньшей размерности, хранимые в каждой вершине, которые по индукционному предположению занимают <math>O(n \log^{d-2} n)</math> памяти. Просуммируем размеры этих range-tree (суммирование по расстоянию до вершины от корня):
<math>\sum_{k=1}^{\log n} 2^k O(\frac{n}{2^k} \log^{d-2} \frac{n}{2^k}) = \sum_{k=1}^{\log n} O(n \log^{d-2} n) = O(n \log^{d-1} n)</math>. QED.
