Изменения
→Основы алгоритма
<tex>R_v \leftarrow Merge_b(Q_v, R_{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>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>.
В итоге, место, требуемое для алгоритма - <tex>O(N)</tex>.
==Примечания==
