333
правки
Изменения
→Алгоритм
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы отрезков, за которые "отвечает" наша вершина, причем левые границы обоих отрезков - включительно, а правые - нет. В дальнейшем будем называть подобную структуру полуинтвервалом.
Запустим рекурсивную процедуру от всего отрезкаполуинтервала (то есть от корневой вершины).
Для текущего состояния проверяем следующие условия :
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нулевое некоторое значение, которое не повлияет на результат запроса на запрашиваемом отрезке.
''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;
''Например'': текущий и искомый <tex>[2..4)</tex>;
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом в зависимости от типа запроса возвращаем значение на текущем отрезкеполуинтервале, как некоторую функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
''Замечание:''
Так как каждый полуинтервал разбивается не более, чем на <tex>O(\log n)</tex> полуинтервал (поскольку на каждом уровне дерева может быть не более двух полуинтервалов из разбиения, а всего уровней <tex>\log n</tex> ), то данная реализация выполняется за <tex>O(\log n)</tex>.
==Пример==
