[[Файл:Down-up1.png|right|255px|thumb|Реализация запроса снизу вверх]]==Алгоритм==
==Алгоритм==Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.
Реализация запроса снизу вверх [[Дерево отрезков. Построение|Построим дерево отрезков]], и установим границы отрезка на соответствующие им листья. Будем действовать в дереве отрезков 3 этапа:# Если элемент, попавший на левую границу, являетсяправым сыном, то запишем в отличие от реализации сверху внизрезультат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, итеративным методома левую границу перемещаем на один элемент вправо. Будем рассматривать дерево отрезков Аналогично с операцией нахождения минимального значенияправой границей (RMQявляется ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. # Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 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> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. '''int''' query(left: '''int''', right: '''int'''): leftRes = ''neutral'' rightRes = ''neutral'' '''while''' left < right '''if''' left '''mod''' 2 == 0 leftRes = leftRes <tex> \circ </tex> data[left] left = left '''div''' 2 '''if''' right '''mod''' 2 == 1 rightRes = data[right] <tex> \circ </tex> rightRes right = right '''div''' 2 - 1 '''if''' left == right leftRes = leftRes <tex> \circ </tex> data[left] '''return''' leftRes <tex> \circ </tex> rightRes ==См.также==* [[Реализация запроса в дереве отрезков сверху]] ==Источники информации==
//Функция нахождения минимального элемента на отрезке <tex>* [left, right]</tex> Min(left, right) result = +inf; //Присваиваем результату максимально возможное значение while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут if ((left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном result = min(result, left.data); // Если является то пересчитаем результат и перенесем левую границу left = (left + 1) / 2; else left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы if ((right) / 2) * 2 + 1 == right http:// Аналогично проделываем операции с правой границей result = min(result, right.data); right = (right e- 1) / 2; else right = (right) / 2; if (left == right) // После окончания цикла проверяем совпали ли границы result = min(result, leftmaxx.data); ru/algo/ Если надо пересчитываем результат return result;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://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 АлгоритмДерево отрезков]]
