Изменения
→Как отвечать на запрос?
Ответ на запрос происходит за <tex>O(\log\,n + answer)</tex> времени.
|proof=
Глубина дерева ровна равна <tex>O(\log\,n)</tex>, значит может быть только <tex>O(\log\,n)</tex> рекурсивных вызовов. В каждой вершине ответ происходит за <tex>O(answer)</tex>, т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответ.
}}
