Изменения
→Постановка задачи
{{notreadyready}}
Рассмотрим задачу хранения множества точек d-мерного пространства с возможностью перечисления точек, содержащихся в d-мерном прямоугольнике запроса. Эту задачу решает range-tree.
Пусть дано пространство <math>X</math>, являющееся произведением <math>d</math> линейных порядков:
<math>X = X_1 \times X_2 \times \hdots dotsm \times X_d</math>.
Отрезком в линейно упорядоченном множестве называется множество <math>[a, b] = \{x | a \leq x \leq b\}</math>.
Прямоугольником в пространстве <math>X</math> назовем произведение отрезков из <math>X_1 \hdots dotso X_d</math>:<math>I = [a_1, b_1] \times [a_2, b_2] \times \hdots dotsm \times [a_d, b_d]</math>, где <math>a_i, b_i \in X_i</math>.
Задача состоит в построении динамической структуры данных, хранящей точки пространства <math>X </math> и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
== Одномерный случай ==
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
* <math>d</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>d-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots dotsm \times X_d</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.
== Fractional cascading ==
Техника ''fractional cascading'' позволяет снизить ассимптотику запроса в range-tree до <math>O(\log^{d - 1} n + k)</math>.
== Упорядоченные последовательности ==
Рассмотрим две упорядоченных последовательности <math>S_1</math> и <math>S_2</math>, причем <math>S_2 \subset S_1</math>.
Пусть стоит задача выдать элементы некоторого отрезка, принадлежащие этим последовательностям.
Очевидно, это можно сделать бинпоиском для каждой последовательности отдельно за <math>O(\log n + k)</math>, где <math>k</math> - размер ответа; тем не менее, это решение никак не использует тот факт, что <math>S_2 \subset S_1</math>.
Теперь, зная, что <math>S_2 \subset S_1</math>, для каждого элемента <math>a_1 \in S_1</math> будем хранить ссылку на минимальный элемент <math>a_2 \in S_2</math>, такой, что <math>a_2 \geq a_1</math>.
В таком случае мы можем избавитсья от двоичного поиске по <math>S_2</math>: после поиска по <math>S_1</math>, мы можем перейти по ссылке, запомненной для первого элемента ответа из <math>S_1</math>, и выдавать элементы из <math>S_2</math>, пока они лежат в отрезке запроса.
Таким образом, запрос для второй последовательности может быть осуществлен за <math>O(1 + k)</math>.
== Layered range-tree ==
<span style="color:#cfcfcf">Попытался передать как можно подробнее. В любом случае советую почитать еще и де Берга на эту тему.</span>
<span style="color:#cfcfcf">Не лишним будет разобраться сначала, скажем, со случаем d=2, он наиболее прост и нагляден.</span>
Рассмотрим d-мерное range-tree и запрос, выполненный до <math>(d-1)</math>-ой координаты.
На последнем шаге мы выбрали набор вершин, поддеревья которых будут обработаны следующим шагом алгоритма (уже по последней координате).
Всегда существует поддерево, содержащее в себе все эти вершины (корнем этого поддерева будет последняя общая вершина в путях от корня дерева к левому и правому концам отрезка запроса).
Корень этого поддерева назовем <math>v_{split}</math>.
Вместо хранения деревьев, мы будем хранить массивы вершин, отсортированные по последней координате.
Заметим, что множества вершин, соответствующие правому и левому детям некоторой вершины, являются подмножествами множества вершин, соответствующему их родителю.
Используем этот факт, чтобы применить ''fractional cascading''. В массивах вместе с вершинами будем хранить ссылку на минимальный элемент массива в левом ребенке, больший или равный текущему элементу массива; аналогично будем хранить ссылки на элементы массива в правом ребенке текущей вершины.
Range-tree с такой оптимизацией называют ''layered range-tree''.
Для осуществления запроса найдем двоичным поиском в массиве, хранящемся в <math>v_{split}</math>, левую границу множества элементов, лежащих в отрезке запроса. Далее, при спуске по дереву (при поиске по предпоследней координате), мы можем поддерживать левую границу текущего поддерева (границу по последней координате), используя сохраненные ссылки. При обработке поддерева по предпоследней координате, используя сохраненный в корне поддерева массив вершин и ссылку на левую границу ответа, мы можем выдать ответ за <math>O(1 + k_v)</math>, где <math>k_v</math> - размер ответа в поддереве вершины <math>v</math>.
Таким образом, мы избавились от поиска по дереву на последнем уровне range-tree, сократив врем работы до <math>O(\log^{d-1} n + k)</math>.
== Ссылки ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страницы 105-109, 112-115.
