1632
правки
Изменения
м
''Замечание.''
При передаче новых параметров следует изменять не только границы, за которые отвечает текущая вершина, но и границы запрашиваемого полуинтервала, чтобы на последующих шагах произошло полное совпадение полуинтервалов.
Рассмотрим данный алгоритм на примере задачи RSQ (запрос суммы на отрезке).
Рассмотрим данную рекурсию:* На глубине <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>[0 .. 8)</tex>, он больше <tex>[1 .. 5) => </tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>
*<tex>[0 .. 4)</tex> выходит за границы<tex> [1 .. 5)</tex>, <tex>[4 .. 8)</tex> выходит за границы <tex>[1 .. 5) => </tex> переходим по рекурсивным вызовам на <tex>[0 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 6)</tex>, <tex>[6 .. 8)</tex>.
*<tex>[0 .. 2)</tex> выходит за границы <tex>[1 .. 5) => </tex> переходим в листья <tex>0, 1 </tex>; <tex>[2 .. 4)</tex> целиком внутри <tex>[1 .. 5) => </tex> возвращаем значение в <tex>[2 .. 4)</tex>; <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) => </tex> возвращаем нулевое значение; <tex>[4 .. 6)</tex> выходит за границы <tex>[1 .. 5) => </tex> переходим к листьям <tex>4</tex> и <tex>5</tex>.
*листья Таким образом ответ на полуинтервале <tex>[1 \ldots 5)</tex> и <tex>0</tex> не пересекается с полуинтервалом равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 5\ldots 2) => </tex> возвращаем нулевое значение, а листья <tex>[2 \ldots 4)</tex> и <tex>1</tex> целиков внутри <tex>[1 .. 4 \ldots 5) => </tex> возвращаем значения в этих листьях.
rollbackEdits.php mass rollback
==Алгоритм==
''Замечание.''
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{- --}} нет).
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. \ldots b)</tex>.[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков]]
В качестве параметров рекурсий передаем следующие переменные:
* <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_4.png|right|602px|Пример рабoты алгоритма]]Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):
* На глубине <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> возвращаем нулевое значение
* На глубине <tex>3</tex>.
** Листья <tex>[1 \ldots 2), [4 \ldots 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
** Листья <tex>[0 \ldots 1), [5 \ldots 6)</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) == [a, b) return tree[node].sum; int m = (l + r) / 2; return get_sum (node * 2 + 1, a, min(b, m)) + get_sum (node * 2 + 2, max(a, m), 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 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
