54
правки
Изменения
→Дерево отрезков
Всего элементарных интервалов не больше <tex>4n+1</tex> (в случае, когда все отрезки не пересекаются: для каждого отрезок левее <tex>x</tex>, <tex>[x : x]</tex>, <tex>(x : x')</tex>, <tex>[x' : x']</tex> и еще один <tex>(p_m : +\infty)</tex>). Так как дерево сбалансированное, его глубина <tex>O(\log n)</tex>.
Утверждается, что один отрезок на одной глубине встречается не более двух раз. Пусть это не так, возьмем из любых трех вершинтри упорядоченные вершины <tex>v_1, содержащих v_2, v_3</tex>, содержащие этот отрезок. Очевидно, среднюю. Ее что сосед <tex>v_2</tex> тоже содержится в этом отрезке, тогда он содержится и содержит этот отрезок (см. картинку). Тогда этот отрезок должен содержаться в родителе этих вершин<tex>parent(v_2)</tex>. Противоречие. [[Файл:Segment_tree_proof.png]]
Глубина <tex>O(\log n)</tex>, всего отрезков <tex>n</tex>, на каждом уровне отрезок встречается <tex>O(1)</tex> раз — победа.
