Реализация запроса в дереве отрезков снизу

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации запроса сверху вниз, итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a [math] \circ [/math] b.

Построим дерево отрезков и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:

1. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева.
2. Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.
3. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.

Псевдокод

Пусть результат считаем на отрезке [left, right]. При этом значения left и right, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).

  query(left, right)
     result = neutral;
     while left < right
        if left mod 2 == 0
           result = result [math] \circ [/math] data[left];
        left = left div 2; 
        if right mod 2 == 1
           result = result [math] \circ [/math] data[right];
        right = (right - 2) div 2;
     if left == right  
        result = result [math] \circ [/math] data[left];
     return result;

Ссылки

MAXimal :: algo :: Дерево отрезков

Википедия — Дерево отрезков

Визуализатор

Алгоритм