Изменения
→Ключевые моменты: - заменил скобки в картинке
Наша задача показать, что все операции с узлом <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_4, 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>.
