Изменения
→Запрос
== Дерево отрезков ==
[[Файл:Segment_tree_1.png|200px400px|thumb|right|Пример дерева отрезков]]
Для решения задачи потребуется структура данных, которая называется дерево отрезков (segment tree). NB: по-русски этими словами принято обозначать несколько [[Дерево_отрезков._Построение | другую]] структуру данных, здесь не о ней.
Построим сбалансированное бинарное дерево, листам которого будут соответствовать элементарные интервалы, а внутренним вершинам — объединения интервалов в потомках.
Будем обозначать интервал, соответствующий вершине <tex>v</tex>, <tex>Int(v)</tex>.
В каждой вершине будем хранить соответствующий ей интервал и множество отрезков <tex>I(v)</tex>, таких что <tex>I(v) \subset I</tex> и <tex>\forall [x : x'] \in I(v) : Int(v) \subset [x : x'], Int(parent(v)) \not\subset [x : x']</tex>. По-человечески это значит, что интервал вершины должен полностью лежать внутри отрезка и выше таких вершин нетдля родителя вершины это не так. По картинке должно быть понятно.
{{Лемма
}}
=== Построение дерева ===
Сначала сортируем концы отрезков из <tex>I</tex> за <tex>O(n \log n)</tex>. За <tex>O(n)</tex> собираем сбалансированное дерево (просто поднимаясь от листьев к корню и объединяя интервалы). Осталось найти <tex>I(v)</tex> для вершин дерева. Для этого вставим туда каждый отрезок по такому алгоритму:
def '''InsertSegment'''(v, [x : x']):
v.Add([x : x'])
else:
if <tex>Int(v.Left) \cap [x : x '] \neq \emptysetvarnothing</tex>:
InsertSegment(v.Left, [x : x'])
if <tex>Int(v.Right) \cap [x : x '] \neq \emptysetvarnothing</tex>:
InsertSegment(v.Right, [x : x'])
Это работает за <tex>O(\log n)</tex>, потому что на каждом уровне есть не более двух вершин, в которые отрезок нужно вставить и еще не более двух вершин, содержащих его концы. Таким образом, на каждом уровне нужно обработать не более четырех вершин. Итого для всех отрезков получаем <tex>O(n \log n)</tex>.
if !v.IsLeaf:
if <tex>p \in Int(v.Left)</tex>:
Query(v.Left, p, S)
else
Query(v.Right, p, S) Query(root, p, <tex>\emptysetvarnothing</tex>)
Запрос работает за <tex>O(\log n + k)</tex>, где <tex>k</tex> — размер ответа.
Таким образом, обработка одной вершины занимает <tex>O(\log n + k_v)</tex> времени, где <tex>k_v</tex> — количество отрезков в ответе, полученных из вершины <tex>v</tex>, всего посещенных вершин <tex>O(\log n)</tex>, итого <tex>O({\log}^2 n + k)</tex>. Препроцессинг выполняется за <tex>O(n {\log}^2 n)</tex> из-за вставки в дерево поиска.
== Ссылки ==
* [https://en.wikipedia.org/wiki/Segment_tree Английская википедия]
* de Berg, van Kreveld, Overmars, Schwarzkopf "Computational Geometry Algorithms and Applications", p. 231
