1632
правки
Изменения
м
rollbackEdits.php mass rollback
Ответ на запрос происходит за <tex>O(\log\,n + answer)</tex> времени.
|proof=
Глубина дерева ровна равна <tex>O(\log\,n)</tex>, значит может быть только <tex>O(\log\,n)</tex> рекурсивных вызовов. В каждой вершине ответ происходит за <tex>O(answer)</tex>, т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответ.
}}
right_segments.add(s);
sort(left_segments) // by increasing of x_mid - segment.left
sort(right_segments) // by increasing decreasing of segment.right - x_mid
result.left = build(left_child);
result.right = build(right_child);
