Изменения

==Описание==[[Файл:Down-up1.png|right|255px|thumb|Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом.]] 

[[Файл:Down-up1.png|right|350px|thumb|Реализация запроса снизу вверх]]в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).<br> Установим границы отрезка на соответствующие листья. Если элемент , попавший на левую границу , является правым сыном, то отрезаем его, левая вычисляем результат как минимум между предыдущем результатом и значением этого элемента. Левая граница перемещается на один элемент вправо; в другом случае . Иначе левую границу не трогаем. Аналогично рассматриваем элемент попавший действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элементПродолжаем до тех пор, мы считаем минимум из отрезанного и минимума на оставшемся отрезке. Закончим алгоритм, когда пока границы не пересекутся.

Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.  //Функция нахождения минимального элемента на отрезке <tex>[left, right]</tex> segmentMinMin(left, right) res result = MAX_INT+inf; //Присваиваем результату максимально возможное значение while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут if isRightSon((left)/ 2) * 2 == left // Проверяем является ли левая граница правым сыном res result = min(resresult, left.data[left]);// Если является то пересчитаем результат и перенесем левую границу left = parent(left + 1)/ 2;

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

right = parent(right)/ 2; if (left == right) // После окончания цикла проверяем совпали ли границы res result = min(resresult, left.data[left]); return res; Функция <tex>parent()</tex> возвращает родителя аргумента.<br>Функции <tex>isLeftSon(), isRightSon()</tex> возвращают является ли элемент правым или левым сыном соответственно.Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.  parent(vertex) return vertex / 2;  isLeftSon(vertex) if parent(vertex) * 2 + 1 == vertex return true;Если надо пересчитываем результат return falseresult;