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

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

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения(RMQ).

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

Псевдокод

Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.

  //Функция нахождения минимального элемента на отрезке [left, right]
  Min(left, right)
     result = +inf; //Присваиваем результату максимально возможное значение
     while left < right //Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
        if ((left) div 2) * 2 + 1 == left // Проверяем, является ли левая граница правым сыном
           result = min(result, data[left]); // Если является, то пересчитаем результат и перенесем левую границу
           left = (left + 1) div 2; 
        else
           left = (left) div 2; // Если не является, то установим границу на родительский элемент текущей границы
        if ((right) div 2) * 2 == right // Аналогично проделываем операции с правой границей
           result = min(result, data[right]);
           right = (right - 1) div 2;
        else
           right = (right) div 2;
     if left == right // После окончания цикла проверяем совпали ли границы  
        result = min(result, data[left]); // Если надо пересчитываем результат
     return result;

Ссылки

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

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

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

Алгоритм