189
правок
Изменения
Нет описания правки
Отсюда и дальше <tex>ls(v)</tex>, <tex>rs(v)</tex> и <tex>ft(v)</tex> означают, соответственно, левого сына, правого сына, и отцовскую вершину узла <tex>v</tex>.
Наша задача показать, что все операции с узлом <tex>v</tex> происходят за <tex>O(|S_v) + |Int(D_v, S_v')| + (a_v - b_v)logN)</tex>, и чтобы показать это, возьмем во внимание, что <tex>\sum_v |S_v| = O(N \cdot logN + K)</tex> (очевидно, что <tex>\sum_v |Int(D_v, S_v')| \le K</tex>).
[[Файл:Balaban_pic_2.png|280px|thumb|right|<tex>S_v = (s_1, s_2, s_3, s_4, s_5)</tex>, <tex>L_v = (s_1, s_3)</tex>, <tex>R_v = (s_3, s_4)</tex>, <tex>I_v = (s_2, s_5)</tex>]]
Функция <tex>TreeSearch</tex> похожа на функцию <tex>SearchInStrip</tex>. Основная разница заключается в том, что <tex>SearchInStrip</tex> вызывает себя без изменения полосы, когда <tex>TreeSearch</tex> делит полосу на две части, после чего рекурсивно вызывает себя для них. Другое отличие заключается в том, что множество <tex>S_v</tex> не упорядочено так же, как <tex>L</tex>. В результате мы не можем напрямую использовать функцию <tex>Split</tex> для эффективного деления <tex>S_v</tex>.
