54
правки
Изменения
Нет описания правки
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
== Одномерный случай ==
Для начала рассмотрим задачу в случае <math>N = 1</math>.
Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.
Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса <math>[a, b]</math>.
Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:
* Запустить обычный поиск в двоичном дереве элементов <math>a</math> и <math>b</math>, остановившись в последней общей вершине пути из корня; назовем эту вершину <math>v</math>.
* Продолжить поиск элемента <math>a</math> из вершины <math>v</math>. При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
* Аналогично, продолжить поиск элемента <math>b</math> из вершины <math>v</math>. При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.
Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.
Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время <math>O(\log n + k)</math>, где <math>n</math> - количество элементов в дереве, <math>k</math> - размер ответа.
