[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
1. # Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей(является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. 2. # Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1), пока границы не пересекутся. 3. # Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
[[Файл:ДО_снизу_вверх.png|800px|Реализация запроса снизу вверх]]
==Псевдокод==
Пусть результат считаем на отрезке [left, right]. При этом значения left и right, передающиеся в функцию left и right , должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).
query(left, right)
