69
правок
Изменения
Нет описания правки
==Алгоритм==
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> a \circ b</tex> b.
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:
==Псевдокод==
Пусть результат считаем на отрезке [<tex> left, right</tex>]. При этом значения <tex>left </tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные left_res <tex>left</tex>_<tex>res</tex> и right_res <tex>right</tex>_<tex>res</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.
'''int''' query(left : '''int''', right : '''int'''):
