Изменения
→Запрос
Построим сбалансированное бинарное дерево, листам которого будут соответствовать элементарные интервалы, а внутренним вершинам — объединения интервалов в потомках.
Будем обозначать интервал, соответствующий вершине <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>. По-человечески это значит, что интервал вершины должен полностью лежать внутри отрезка и выше таких вершин нетдля родителя вершины это не так. По картинке должно быть понятно.
{{Лемма
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> — размер ответа.
