81
правка
Изменения
Нет описания правки
== Определение ==
Дерево интервалов (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-ой_порядковой_статистики_за_линейное_время]]). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от <tex>x_{mid}</tex> и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают <tex>x_{mid}</tex>. В одном отсортируем их по левой координате, в другом {{---}} по правой.
{{Теорема
|statement=
Дерево интервалов имеет глубину <tex>O(\log\,n)</tex>.
|proof=
При каждом рекурсивном вызове построения дерева множество концов отрезков уменьшается более чем в два раза. Значит, после <tex>O(\log\,n)</tex> рекурсивных вызовов, множество отрезков будет пусто.
}}
{{Теорема
|statement=
Дерево интервалов занимает <tex>O(n)</tex> памяти.
|proof=
По построению каждый отрезок был добавлен ровно в два списка. Вершин в двоичном дереве глубины <tex>O(\log\,n)</tex>, очевидно, <tex>O(n)</tex>.
}}
{{Теорема
|statement=
Построение дерева интервалов работает за <tex>O(n\log\,n)</tex> времени.
|proof=
Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина <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> для построения всего дерева.
}}
