54
правки
Изменения
Нет описания правки
Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время <math>O(\log n + k)</math>, где <math>n</math> - количество элементов в дереве, <math>k</math> - размер ответа.
== Многомерный случай ==
Теперь рассмотрим общий, многомерный случай задачи. Для её решения будем использовать структуру данных под названием range-tree.
Дадим следующее рекурсивное определение range-tree:
* Одномерное range-tree {{---}} просто дерево поиска, описанное выше.
* <math>N</math>-мерное range-tree {{---}} дерево поиска (по первой координате <math>X_1</math>), аналогичное описанному выше, но в каждой вершине дополнительно хранящее <math>N-1</math>-мерное range-tree (по остальным координатам <math>X_2 \times \hdots \times X_N</math>) для множества элементов, являющихся листами поддерева этой вершины.
Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:
* Выполнить описанную выше процедуру поиска элементов отрезка для проекции прямоугольника запроса на <math>X_1</math>.
* При добавлении поддерева к ответу:
** Если текущая координата - последняя, выдать все листы поддерева в качестве ответа
** Если текущая координата - не последняя, перейти к сохраненному в корне поддерева range-tree по следующим координатам и повторить тот же алгоритм.
Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.
