403
правки
Изменения
м
→Построение дерева
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>.
