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