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

Описание

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.

Алгоритм

Реализация запроса снизу вверх

Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).
Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то отрезаем его, левая граница перемещается на один элемент вправо; в другом случае левую границу не трогаем. Аналогично рассматриваем элемент попавший на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элемент, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда границы пересекутся.

Псевдокод

Псевдокод функции нахождения минимума на отрезке [math][left, right][/math].

  segmentMin(left, right)
     res = MAX_INT; 
     while left < right
        if isRightSon(left)
           res = min(result, data[left]);
           left = parent(left + 1);
        else
           left = parent(left);
        if isLeftSon(right)
           result = min(result, data[right]);
           right = parent(right - 1);
        else
           right = parent(right);
        if left == right
           result = min(result, data[left]);
        return result;

Функция [math]parent()[/math] возвращает родителя аргумента.
Функции [math]isLeftSon(), isRightSon()[/math] возвращают является ли элемент правым или левым сыном соответственно. Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.

  parent(vertex)
     return vertex / 2;

  isLeftSon(vertex)
     if parent(vertex) * 2 + 1 == vertex
        return true;
     return false;

Ссылки

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

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

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

Алгоритм