Изменения

 Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Файл:Down-up.png|right|350pxРеализация запроса в дереве отрезков сверху|thumb|Реализация реализации запроса снизу вверхсверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>. [[Дерево отрезков. Построение|Построим дерево отрезков с операцией нахождения минимального значения ]], и установим границы отрезка на отрезке(RMQ)соответствующие им листья.<br>Будем действовать в 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 ''' 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 ''' 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 ==См. также==* [[Реализация запроса в дереве отрезков сверху]] ==Источники информации== * [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков] * [http://ru.wikipedia.org/wiki/%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 Википедия {{---}} Дерево отрезков] * [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]

[http[Категория://e-maxx.ru/algo/segment_tree - MAXimal :: algo :: Дерево отрезковДискретная математика и алгоритмы]]

[http[Категория://ru.wikipedia.org/wiki/%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 - Дерево отрезков — Википедия]]