333
правки
Изменения
→Алгоритм
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
Так как каждый полуинтервал разбивается не более, чем на <tex>O(\log n)</tex> полуинтервалов (поскольку на каждом уровне дерева рекурсия может быть дойти до не более , чем двух полуинтервалов из разбиениявершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок предыдущего уровня), а всего уровней <tex>\log n</tex> ), то данная реализация выполняется за <tex>O(\log n)</tex>.
==Пример==
