1632
правки
Изменения
м
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex>
* На глубине 3. ** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение Таким образом ответ на полуинтервале <tex>[1 .. \ldots 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. \ldots 2)</tex>, <tex>[2 .. \ldots 4)</tex> и <tex>[4 .. \ldots 5)</tex>.
rollbackEdits.php mass rollback
==Алгоритм==
''Замечание.''
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{- --}} нет).
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. \ldots b)</tex>.
В качестве параметров рекурсий передаем следующие переменные:
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
Для текущего состояния проверяем следующие условия :
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
:''Например'': текущий <tex>[1..\ldots 3)</tex>, а искомый <tex>[3 .. \ldots 5)</tex>;
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
:''Например'': текущий <tex>[2..\ldots 3)</tex>, а искомый <tex>[2..\ldots 4)</tex>;
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
==Пример==
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ }</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операций операции на этих детях.
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
{{---}} это отрезок <tex>[1 .. \ldots 4]</tex> (полуинтервал <tex>[1 .. \ldots 5)</tex>).[[Файл:Image_3Image_4.png|right|601px602px|Пример рабoты алгоритма]]Рассмотрим данный алгоритм на определенных глубинах рекурсии (, то есть на разных уровнях дерева(на рисунке глубина обозначена слева от уровня):
* На глубине <tex>0</tex>. (на рисунке глубина обозначена слева от уровня). ** Текущий полуинтервал <tex>[0 .. \ldots 8)</tex> пересекается с <tex>[1 .. \ldots 5) \Rightarrow</tex> рекурсивно переходим по рекурсивным вызовам на к <tex>[0 .. \ldots 4)</tex> и <tex>[4 .. \ldots 8)</tex>
* На глубине <tex>1</tex>.
** <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex> пересекаются с <tex> [1 \ldots 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 \ldots
2)</tex>, <tex>[2 \ldots 4)</tex>, <tex>[4 \ldots 6)</tex> и <tex>[6 \ldots 8)</tex>
* На глубине <tex>2</tex>.
** <tex>[0 \ldots 2)</tex> и <tex>[4 \ldots 6)</tex> пересекаются с <tex>[1 \ldots 5) \Rightarrow </tex> переходим в листья <tex>[0 \ldots 1), [1 \ldots 2), [4 \ldots 5), [5 \ldots 6) </tex>
** <tex>[2 \ldots 4) </tex> полностью лежит внутри <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
** <tex>[6 \ldots 8)</tex> не пересекается с <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем нулевое значение
* На глубине 2. ** <tex>[0 .. 2)3</tex> и <tex>[4 .. 6)</tex> пересекаются с ** Листья <tex>[1 .. 5\ldots 2) \Rightarrow </tex> переходим в листья <tex>0, 1, [4, \ldots 5 </tex>** <tex>[2 .. 4) </tex> полностью лежит внутри лежат в запрашиваемом интервале <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезкезначения в них** Листья <tex>[0 \ldots 1), [5 \ldots 6 .. 8)</tex> не пересекается с лежат вне <tex>[1 .. \ldots 5) \Rightarrow </tex> возвращаем нулевое нейтральное значение
==Реализация==
Рассмотрим реализацию задачи RSQо дереве отрезков с произвольной ассоциативной бинарной операцией.
Пусть в узлах дерева хранятся структуры из трех полей:
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> sum\mathtt{res}</tex> {{---}} сумма результат операции на полуинтервале. <code> int get_sum (int node, int a, int b) { l = tree[node].left; r = tree[node].right; if [l, r) <tex>\bigcap </tex> [a, b) == <tex> \varnothing</tex> return 0; if [l, r) <tex>\subset</tex> [a, b) return tree[node].sum; return get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b); } </code>
'''int''' query('''int''' node, '''int''' a, '''int''' b) l =tree[node].left r =Ссылкиtree[node].right '''if''' [l, r) <tex>\cap </tex> [a, b) ==<tex>\varnothing</tex> '''return''' ''<tex>\varepsilon</tex>'' <span style="color:#008000">// <tex>\varepsilon</tex> {{---}} нейтральный для данной операции элемент</span> '''if''' [l, r) <tex>\subset</tex> [a, b) '''return''' tree[node].res '''return''' query(node * 2 + 1, a, b) <tex> \circ </tex> query(node * 2 + 2, a, b)
==См. также==* [[Реализация запроса в дереве отрезков снизу]]* [[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков. Построение]]
==Источники информации==* [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 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
