Изменения
→Запрос
Построим сбалансированное бинарное дерево, листам которого будут соответствовать элементарные интервалы, а внутренним вершинам — объединения интервалов в потомках.
Будем обозначать интервал, соответствующий вершине <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>. По-человечески это значит, что интервал вершины должен полностью лежать внутри отрезка и выше таких вершин нетдля родителя вершины это не так. По картинке должно быть понятно.
{{Лемма
v.Add([x : x'])
else:
if <tex>Int(v.Left) \cap [x : x '] \neq \varnothing</tex>:
InsertSegment(v.Left, [x : x'])
if <tex>Int(v.Right) \cap [x : x '] \neq \varnothing</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>\varnothing</tex>)
Запрос работает за <tex>O(\log n + k)</tex>, где <tex>k</tex> — размер ответа.
