Изменения

 Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Файл:Down-up1.pngРеализация запроса в дереве отрезков сверху|right|350px|thumb|Реализация реализации запроса снизу вверхсверху вниз]], итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения на отрезке(RMQ).абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b<br/tex>. Установим [[Дерево отрезков. Построение|Построим дерево отрезков]], и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:# Если элемент , попавший на левую границу , является правым сыном, то отрезаем егозапишем в результат значение, левая граница перемещается полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо; в другом случае левую границу не трогаем. Аналогично рассматриваем элемент попавший на правую границу с правой границей (является ли этот элемент она левым сыном). Затем устанавливаем Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. # Устанавливаем границы отрезка на родительские элементы текущих границ. Отрезая элементЭто позволит узнать, мы считаем минимум из отрезанного и минимума на оставшемся отрезкевходит ли полученный отрезок в искомый или нет. Закончим алгоритмПовторяем этап 1, когда пока границы не пересекутся.# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат. {| cellpadding="10"| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''|-| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]|-| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]|-| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]|-| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]|}

Пусть результат считаем на отрезке <tex> [left, right] </tex>. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.   segmentMin'''int''' query(left: '''int''', right: '''int'''): res leftRes = MAX_INT; ''neutral'' rightRes = ''neutral'' '''while ''' left < right '''if isRightSon(''' left)'''mod''' 2 == 0 res leftRes = min(result, leftRes <tex> \circ </tex> data[left]); left = parent(left + 1); else left = parent(left);'''div''' 2 '''if isLeftSon(''' right)'''mod''' 2 == 1 result rightRes = min(result, data[right]);<tex> \circ </tex> rightRes right = parent(right '''div''' 2 - 1); else right = parent(right); '''if ''' left == right result leftRes = min(result, leftRes <tex> \circ </tex> data[left]); '''return result;''' leftRes <tex> \circ </tex> rightRes

Функция <tex>parent()</tex> возвращает родителя аргумента==См.также==Функции <tex>isLeftSon(), isRightSon()</tex> возвращают является ли элемент правым или левым сыном соответственно.Пусть дерево * [[Реализация запроса в дереве отрезков реализовано на массиве с индексацией элементов с 1.сверху]]

isLeftSon(vertex) if parent(vertex) * 2 + 1 == vertex return true; return false;[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]

* [http://e-maxxrain.ifmo.ru/algocat/view.php/vis/segment_tree MAXimal :: algo :: Дерево отрезковtrees/segment-2006 Визуализатор]

* [http://rain.ifmo.ru/cat/view.wikipedia.orgphp/vis/trees/wikisegment-2006/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедияalgorithm Алгоритм]

[http[Категория://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 ВизуализаторДискретная математика и алгоритмы]]

[http[Категория://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm АлгоритмДерево отрезков]]