Изменения
→Основы алгоритма
Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Соединим каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Соответствующим узлом отметим все значения, множества и параметры вызова. Обозначим множество внутренних вершин за <tex>V</tex>.
<tex>IntersectingPairs(S_v, a, bS_0):</tex>
Отсортируем <tex>2 \cdot N</tex> вершин по координатам и
найдем <tex>p_i, s(i), i = 1,...,2 \cdot N;\ S_r \leftarrow S_0</tex>
<tex>TreeSearch(S_r, 1, 2 \cdot N)</tex>;
<tex>TreeSearch(S_rS_v, a, b):</tex>
<tex>\{</tex>
'''if''' <tex>b - a = 1</tex> '''then'''
<tex>\{</tex>
<tex>L \leftarrow</tex> отсортируем <tex>S_v</tex> по отношению <tex><_b_a</tex>;
<tex>SearchInStrip_{a, b}(L_v, R_v)</tex>;
'''return''';
Отсюда и дальше <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>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>.
Неупорядоченные множества <tex>I_{ls(v)}</tex> и <tex>I_{rs(v)}</tex> строятся легко. Множество <tex>L_{ls(v)}</tex> будет найдено вызовом функции <tex>Split_{a, b}(L_v, Q_v, L_{ls(v)})</tex> для третьего шага нахождения <tex>Int(D_v, S_v')</tex> в функции <tex>TreeSearch</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> за линейное время вставкой (если <tex>p_c</tex> левый конец левая вершина отрезка) или удалением (если <tex>p_c</tex> правый конец правая вершина отрезка) отрезка <tex>s(c)</tex>. Но как получить <tex>R_{ls(v)}</tex> из <tex>L_v</tex>, <tex>R_v</tex> и <tex>I_v</tex> без сортировки?
Для листьев мы сделаем проверку вначале, и получим <tex>R_v</tex> из <tex>L_v</tex>. Пусть <tex>L_v</tex> и <tex>I_v</tex> известны, и все сыновья узла <tex>v</tex> - листья. Для начала запустим функцию <tex>Split(L_v, Q_v, L_{ls(v)})</tex> и найдем <tex>Q_v</tex> и <tex>L_{ls(v)}</tex>. Теперь мы должны найти <tex>Int(D_s, S_v') = Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v) \cup Int(D_v, R_{rs(v)})</tex>, но мы не знаем <tex>R_{rs(v)}</tex>и, и соответственно , можем найти только <tex>Int(D_v, L_{ls(v)}) \cup Int(D_v, I_v)</tex>. Применим <tex>SearchInStrip</tex> к множеству <tex>L_{ls(v)}</tex> и получим <tex>R_{ls(v)}</tex>. Множество <tex>L_{rs(v)}</tex> получается из <tex>R_{ls(v)}</tex> вставкой или удалением отрезка <tex>s(c)</tex>. Применим <tex>SearchInStrip</tex> к <tex>L_{rs(v)}</tex> и найдем <tex>R_{rs(v)}</tex>. Теперь можем продолжить вычисление <tex>Int(D_v, R_{rs(v)})</tex> и получим <tex>R_v</tex> слиянием <tex>Q_v</tex> и <tex>R_{rs(v)}</tex>.
Конечная функция будет выглядеть так:
Найдем <tex>Int(D_v, L_{ls(v)})</tex>;
<tex>c \leftarrow \lfloor (a + b) / 2 \rfloor</tex>;
внутренние для полосы <tex>\langle a, c \rangle</tex> во множество <tex>I_{ls(v)}</tex>
внутренние для полосы <tex>\langle c, b \rangle</tex> во множество <tex>I_{rs(v)}</tex>
<tex>\}</tex>
Заметим, что нахождение <tex>Int(D_v, R_{rs(v)})</tex> надо делать аккуратно, так как множества <tex>R_{rs(v)}</tex> и <tex>L_{ls(v)}</tex> могут иметь одни и те же отрезки (которые '''пересекают''' <tex>\langle a, b \rangle</tex>). Мы нашли их пересечения с <tex>D_v</tex> на 3ем шагепри поиске <tex>Int(D_v, L_{ls(v)})</tex>, и не должны вывести эти пересечения снова.
Для начала рассчитаем место, необходимое для выполнения алгоритма. Алгоритм использует рекурсивную функцию <tex>TreeSearch</tex>. Последовательность вызовов функции может занять память. Эта последовательность может быть представлена как путь корня рекурсивного дерева, до узла. Назовем этот узел, и соответствующий вызов ''активным''. Активный вызов занимает <tex>O(N)</tex> памяти, каждый его "предок" занимает <tex>O(|I_v| + |Q_v|)</tex> памяти, а остальные структуры используют <tex>O(N)</tex>. Очевидно, что любой путь <tex>pt</tex> от корня рекурсивного дерева до какого-то узла <tex>\sum_{v \in pt}(|I_v + |Q_v|) = O(N)(|I_v| \le b_v - a_v \le \lceil (b_{ft(v)} - a_{ft(v)})/2 \rceil)</tex>.
