Изменения

Перейти к: навигация, поиск

Реализация запроса в дереве отрезков снизу

1046 байт добавлено, 19:18, 4 сентября 2022
м
rollbackEdits.php mass rollback
==Алгоритм==
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> a \circ b</tex> b.
[[Дерево отрезков. Построение|Построим дерево отрезков]] , и установим границы отрезка на соответствующие им листья. Будем действовать в 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.png‎jpg|800px550px]]|Реализация запроса -| [[Файл:Запрос снизу №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'''): result leftRes = ''neutral;'' rightRes = ''neutral''
'''while''' left < right
'''if''' left '''mod ''' 2 == 0 result leftRes = result leftRes <tex> \circ </tex> data[left]; left = left '''div ''' 2; '''if''' right '''mod ''' 2 == 1 result rightRes = result data[right] <tex> \circ </tex> data[right];rightRes right = (right - 2) '''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/algo/segment_tree MAXimal :: algo :: Дерево отрезков]==Источники информации==
* [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 АлгоритмВизуализатор]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
1632
правки

Навигация