Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
Версия от 20:06, 7 января 2014; Qwerty787788 (обсуждение | вклад)
Конспект не готов. |
Определение
Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков
и множество запросов. Каждый запрос характеризуется точкой . Для каждого запроса необходимо определить множество отрезков из , которые содержат в себе . Построение дерева интервалов занимает время , а также памяти. На каждый запрос дерево интервалов позволяет отвечать за , где — размер ответа на запрос.Построение
Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков Поиск_k-ой_порядковой_статистики_за_линейное_время). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают . В одном отсортируем их по левой координате, в другом — по правой.
. Это можно сделать за (см.Теорема: |
Дерево интервалов имеет глубину . |
Доказательство: |
При каждом рекурсивном вызове построения дерева множество концов отрезков уменьшается более чем в два раза. Значит, после | рекурсивных вызовов, множество отрезков будет пусто.
Теорема: |
Дерево интервалов занимает памяти. |
Доказательство: |
По построению каждый отрезок был добавлен ровно в два списка. Вершин в двоичном дереве глубины | , очевидно, .
Теорема: |
Построение дерева интервалов работает за времени. |
Доказательство: |
Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина | , требуется времени. Теперь рассмотрим время, необходимое для рекурсивных вызовов. Для каждой вершины дерева это время равно , где — количество отрезков, которые были переданы рекурсивно. Просуммируем это время по всем "слоям" дерева. Под каждым слоем понимаются все вершины дерева, которые лежат на одной и той же глубине. Т. к. в каждом слое множества отрезков для любых двух вершин не пересекаются, то суммарное количество отрезков в слое равно . Слоев всего , значит, имеем общую оценку для построения всего дерева.
Как отвечать на запрос?
В каждой вершине дерева хранится
, ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают . Рассмотрим два симметричных случая. Например, . Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать ). Аналогично разбирается случай .Теорема: |
Ответ на запрос происходит за времени. |
Доказательство: |
Глубина дерева ровна | , значит может быть только рекурсивных вызовов. В каждой вершине ответ происходит за , т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответе.