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