Просмотр исходного текста страницы Дерево интервалов (interval tree) и пересечение точки с множеством интервалов

== Построение ==
Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков <tex>x_{mid}</tex>. Это можно сделать за <tex>O(n)</tex> (см. [[Поиск k-ой порядковой статистики за линейное_время | Поиск 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> для построения всего дерева.
}}