403
правки
Изменения
м
→Построение
Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков <tex>I=\{[x_1, x'_1], \ldots, [x_n, x'_n]\}</tex> и множество запросов. Каждый запрос характеризуется точкой <tex>q_x</tex>. Для каждого запроса необходимо определить множество отрезков из <tex>I</tex>, которые содержат в себе <tex>q_x</tex>. Построение дерева интервалов занимает время <tex>O(n \log\,n)</tex>, а также <tex>O(n)</tex> памяти. На каждый запрос дерево интервалов позволяет отвечать за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} размер ответа на запрос.
== Построение ==
Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков <tex>x_{mid}</tex>. Это можно сделать за <tex>O(n)</tex> (см. [[Поиск_kПоиск k-ой_порядковой_статистики_за_линейное_времяой порядковой статистики за линейное_время | Поиск k-ой порядковой статистики]]). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от <tex>x_{mid}</tex> и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают <tex>x_{mid}</tex>. В одном отсортируем их по левой координате, в другом {{---}} по правой.
{{Теорема
|statement=
Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина <tex>O(n)</tex>, требуется <tex>O(n\log\,n)</tex> времени. Теперь рассмотрим время, необходимое для рекурсивных вызовов. Для каждой вершины дерева это время равно <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество отрезков, которые были переданы рекурсивно. Просуммируем это время по всем <tex>O(\log\,n)</tex> "слоям" дерева. Под каждым слоем понимаются все вершины дерева, которые лежат на одной и той же глубине. Т. к. в каждом слое множества отрезков для любых двух вершин не пересекаются, то суммарное количество отрезков в слое равно <tex>O(n)</tex>. Слоев всего <tex>O(\log\,n)</tex>, значит, имеем общую оценку <tex>O(n\log\,n)</tex> для построения всего дерева.
}}
== Как отвечать на запрос? ==
В каждой вершине дерева хранится <tex>x_{mid}</tex>, ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают <tex>x_{mid}</tex>. Необходимо рассмотреть два симметричных случая. Покажем, что делать в одном из них. Пусть, например, <tex>q_x>x_{mid}</tex>. Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать <tex>q_x</tex>). Аналогично разбирается случай <tex>q_x < x_{mid}</tex>.
