Изменения
→Основы алгоритма
<tex>TreeSearch(S_{rs}(v), c, b)</tex>;
<tex>\}</tex>
Отсюда и дальше <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>.
Чтобы решить эту проблему, представим <tex>S_v</tex> как объединение трех множеств:
множества <tex>L_v</tex> упорядоченного по отношению <tex><_a</tex>, неупорядоченного множества <tex>I_v</tex>, и множества <tex>R_v</tex> упорядоченного по отношению <tex><_b</tex>. Расположим отрезки из <tex>S_v</tex>, пересекающие границу <tex>x = a</tex> во множество <tex>L_v</tex>, отрезки пересекающие <tex>x = b</tex> во множество <tex>R_v</tex>, и внутренние отрезки во множество <tex>I_v</tex> (пример на ''рисунке справа'').
Теперь мы можем вызвать функцию <tex>Split</tex> для множества <tex>L_v</tex> и построить <tex>Q_v</tex> за <tex>O(|L_v|) = O(|S_v|)</tex> времени. Но мы натыкаемся на новую проблему: передавая множества <tex>L_v</tex>, <tex>I_v</tex> и <tex>R_v</tex>, необходимо найти соответствующие множества сыновей узла <tex>v</tex>.
