54
правки
Изменения
Fractional cascading
<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>.
