Изменения

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

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

Пусть дерево отрезков реализовано ассоциативная операция выполняется функцией operation(arg1, arg2), а результат считаем на массиве с индексацией элементов с 1отрезке [left, right].

//Функция нахождения минимального элемента на отрезке [left, right] Minrealization(left, right) result = +infstart_value; //Присваиваем результату максимально возможное начальное значение (например для поиска суммы надо присвоить значение0)

if ((left) div 2) * 2 + 1 == left // Проверяем, является ли левая граница правым сыном(индексация с 0) result = minoperation(result, data[left]); // Если является, то пересчитаем результат и перенесем левую границу

left = (left) div 2; // Если не является, то установим границу на родительский элемент текущей границы if ((right) div 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей result = minoperation(result, data[right]);

right = (right) div 2;

result = minoperation(result, data[left]); // Если надо пересчитываем результат