Дерево интервалов (interval tree) и пересечение точки с множеством интервалов

Конспект не готов.

Определение

Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков [math]I=\{[x_1, x'_1], \ldots, [x_n, x'_n]\}[/math] и множество запросов. Каждый запрос характеризуется точкой [math]q_x[/math]. Для каждого запроса необходимо определить множество отрезков из [math]I[/math], которые содержат в себе [math]q_x[/math]. Построение дерева интервалов занимает время [math]O(n \log\,n)[/math], а также [math]O(n)[/math] памяти. На каждый запрос дерево интервалов позволяет отвечать за [math]O(\log\,n + k)[/math], где [math]k[/math] — размер ответа на запрос.

Построение

Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков [math]x_{mid}[/math]. Это можно сделать за [math]O(n)[/math] (см. Поиск_k-ой_порядковой_статистики_за_линейное_время). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от [math]x_{mid}[/math] и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают [math]x_{mid}[/math]. В одном отсортируем их по левой координате, в другом — по правой.

Теорема:

Дерево интервалов имеет глубину [math]O(\log\,n)[/math].

Доказательство:

[math]\triangleright[/math]

При каждом рекурсивном вызове построения дерева множество концов отрезков уменьшается более чем в два раза. Значит, после [math]O(\log\,n)[/math] рекурсивных вызовов, множество отрезков будет пусто.

[math]\triangleleft[/math]

Теорема:

Дерево интервалов занимает [math]O(n)[/math] памяти.

Доказательство:

[math]\triangleright[/math]

По построению каждый отрезок был добавлен ровно в два списка. Вершин в двоичном дереве глубины [math]O(\log\,n)[/math], очевидно, [math]O(n)[/math].

[math]\triangleleft[/math]

Теорема:

Построение дерева интервалов работает за [math]O(n\log\,n)[/math] времени.

Доказательство:

[math]\triangleright[/math]

Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина [math]O(n)[/math], требуется [math]O(n\log\,n)[/math] времени. Теперь рассмотрим время, необходимое для рекурсивных вызовов. Для каждой вершины дерева это время равно [math]O(m)[/math], где [math]m[/math] — количество отрезков, которые были переданы рекурсивно. Просуммируем это время по всем [math]O(\log\,n)[/math] "слоям" дерева. Под каждым слоем понимаются все вершины дерева, которые лежат на одной и той же глубине. Т. к. в каждом слое множества отрезков для любых двух вершин не пересекаются, то суммарное количество отрезков в слое равно [math]O(n)[/math]. Слоев всего [math]O(\log\,n)[/math], значит, имеем общую оценку [math]O(n\log\,n)[/math] для построения всего дерева.

[math]\triangleleft[/math]

Как отвечать на запрос?

В каждой вершине дерева хранится [math]x_{mid}[/math], ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают [math]x_{mid}[/math]. Рассмотрим два симметричных случая. Например, [math]q_x\gt x_{mid}[/math]. Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать [math]q_x[/math]). Аналогично разбирается случай [math]q_x \lt x_{mid}[/math].

Теорема:

Ответ на запрос происходит за [math]O(\log\,n + answer)[/math] времени.

Доказательство:

[math]\triangleright[/math]

Глубина дерева ровна [math]O(\log\,n)[/math], значит может быть только [math]O(\log\,n)[/math] рекурсивных вызовов. В каждой вершине ответ происходит за [math]O(answer)[/math], т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответе.

[math]\triangleleft[/math]