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>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершинвершина.
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
Для текущего состояния проверяем следующие условия :
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
:''Например'': текущий <tex>[1..\ldots 3)</tex>, а искомый <tex>[3 .. \ldots 5)</tex>;
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
:''Например'': текущий <tex>[2..\ldots 3)</tex>, а искомый <tex>[2..\ldots 4)</tex>;
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
Так как каждый полуинтервал разбивается не более, чем на <tex>O(\log n)</tex> полуинтервалов (поскольку на каждом уровне дерева рекурсия может быть дойти до не более , чем двух полуинтервалов из разбиениявершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex> ), то данная реализация операция выполняется за <tex>O(\log n)</tex>.
==Пример==
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ }</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операций операции на этих детях.
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
{{---}} это отрезок <tex>[1 .. \ldots 4]</tex> (полуинтервал <tex>[1 .. \ldots 5)</tex>).[[Файл:Image_2Image_4.png|right|600px602px|Пример работы раб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; int m = (l + r) / 2; return get_sum (node * 2 + 1, a, m) + get_sum (node * 2 + 2, m + 1, 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 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
