Изменения

Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве Дерево отрезков сверху. Построение| реализации запроса сверху внизПостроим дерево отрезков]], итеративным методоми установим границы отрезка на соответствующие им листья. Будем рассматривать абстрактную операциюдействовать в 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>, над которой построено дерево отрезковпередающиеся в функцию, обозначается a должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex> \circ leftRes</tex> b, а результат считаем и <tex>rightRes</tex> будут собирать значения на отрезке [leftотрезках, right]отделившихся соответственно слева или справа от рассматриваемого.

'''int''' query(left: '''int''', right: '''int'''): result leftRes = ''neutral; //Присваиваем результату значение нейтральное элемента(например для поиска суммы надо присвоить значение 0)'' rightRes = ''neutral'' '''while ''' left < right //Выполняем цикл до тех пор, пока левая и правая граница не пересекутся '''if (''' left div 2) * '''mod''' 2 == left // Проверяем, является ли левая граница правым сыном (индексация с 0) result leftRes = result leftRes <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу left = (left + 1) div 2; else left = left '''div ''' 2; // Если не является, то установим границу на родительский элемент текущей границы '''if (''' right div '''mod''' 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей1 result rightRes = result data[right] <tex> \circ </tex> data[right]; right = (right - 1) div 2;rightRes else right = right '''div ''' 2;- 1 '''if ''' left == right // После окончания цикла проверяем совпали ли границы result leftRes = result leftRes <tex> \circ </tex> data[left]; // Если надо пересчитываем результат '''return result;''' leftRes <tex> \circ </tex> rightRes

==СсылкиСм. также==* [[Реализация запроса в дереве отрезков сверху]]

* [http://e-maxx.ru.wikipedia.org/wikialgo/%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 Википедия {{---}} segment_tree MAXimal :: algo :: Дерево отрезков]

* [http://rainru.ifmowikipedia.ruorg/catwiki/view.php/vis/trees/segment%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 Википедия {{---2006 Визуализатор}} Дерево отрезков]

* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm АлгоритмВизуализатор]