189
правок
Изменения
→Основной алгоритм: Приподнял картинку
<tex>TreeSearch(S_{rs}(v), c, b)</tex>;
<tex>\}</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>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>).
Функция <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>(пример на рисунке справа).
==Примечания==
