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