1632
правки
Изменения
м
Будем рассматривать запрос на примере задачи RSQ''Замечание.''Используем в алгоритме не отрезки, а полуинтервалы (запрос суммылевая граница включительно, а правая {{---}} нет). Пусть есть уже [[Файл:123Дерево отрезков.jpg|right|380px|thumbПостроение|Пример дерева построенное дерево отрезков для вычисления сумм]] и идет запрос на полуинтервале <tex>[a \ldots b)</tex>. В качестве параметров рекурсий передаем следующие переменные:Если запрашиваемый отрезок не пересекается * <tex>node</tex> {{---}} номер (в массиве с рассматриваемым отрезком, возвращаем нейтральный элементдеревом отрезков) текущей вершины дерева.Если запрашиваемый отразив совпадает с запрашиваемый* <tex>a</tex>, возвращаем значение в вершине<tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.Иначе считаем для подотрезков рекурсивноПусть <tex>l</tex>, комбинируем ответ <tex>r</tex> {{---}} это левая и возвращаем значениеправая границы полуинтервала, за которые "отвечает" наша вершина.Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
[[Файл:Отрезки.JPG|right|380px|thumb|Дерево отрезков]]
1При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей)Текущий отрезок [1 .. 8], он больше [2 .. 5] => переходим по рекурсивным вызовам равна сумме результатов выполнения операции на [1 .. 4] и [5 .этих детях. 8]
2)[1 * На глубине <tex>0</tex>.. 4] выходит за границы ** Текущий полуинтервал <tex>[2 .. 5], [5 .. 0 \ldots 8] выходит за границы )</tex> пересекается с <tex>[2 .. 1 \ldots 5] =) \Rightarrow</tex> рекурсивно переходим по рекурсивным вызовам на [1 .. 2], к <tex>[3 .. 0 \ldots 4] )</tex> и <tex>[5 .. 6], [7 .. 4 \ldots 8].)</tex>
3)[* На глубине <tex>1 </tex>.. 2] выходит за границы ** <tex>[2 .. 5] =0 \ldots 4)</tex> и <tex> переходим в листья 1, 2; [3 .. 4] целиком внутри \ldots 8)</tex> пересекаются с <tex> [2 .. 1 \ldots 5] =) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex> возвращаем значение в [3 .. 4];0 \ldots[7 .. 8] не пересекается с 2)</tex>, <tex>[2 .. 5] =\ldots 4)</tex> возвращаем нулевое значение, <tex>[5 .. 4 \ldots 6] выходит за границы [2 .. 5] =)</tex> переходим к листьям 5 и <tex>[6\ldots 8)</tex>
int sum (int v, int tl, int tr, int l, int r) { if ([l,r] не пересекается с [tl, tr]) return 0; if (l == tl && r См. также== tr) return t* [v[Реализация запроса в дереве отрезков снизу]]; int tm = (tl + tr) / 2; return sum (v*2, tl, tm, l, min(r,tm)) + sum (v*2+1, tm+1, tr, max(l,tm+1), r); } </code>[[Дерево отрезков. Построение]]
rollbackEdits.php mass rollback
Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.
==Алгоритм==
Для текущего состояния проверяем следующие условия:
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
:''Например'': текущий <tex>[1 \ldots 3)</tex>, а искомый <tex>[3 \ldots 5)</tex>;
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
:''Например'': текущий <tex>[2 \ldots 3)</tex>, а искомый <tex>[2 \ldots 4)</tex>;
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.
==Пример==
Рассмотрим работу программы данный алгоритм на дереве отрезков для элементов [1 .. 8].Пусть запрашиваемая сумма примере задачи <tex>\mathrm{RSQ}</tex> (Range Sum Query {{- это отрезок [2 .. 5]--}} запрос суммы на отрезке).
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма
{{---}} это отрезок <tex>[1 \ldots 4]</tex> (полуинтервал <tex>[1 \ldots 5)</tex>).
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]
Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):
* На глубине <tex>2</tex>. ** <tex>[0 \ldots 2)</tex> и <tex>[4\ldots 6)лист 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>[2 .. 1 \ldots 5) \Rightarrow </tex> возвращаем сумму на этом отрезке** <tex>[6 \ldots 8)</tex> не пересекается с <tex>[1 \ldots 5] =) \Rightarrow </tex> возвращаем нулевое значение в листе 5.
* На глубине <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> возвращаем нейтральное значение
Таким образом ответ на полуинтервале <tex>[1 \ldots 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2)</tex>, <tex>[2 \ldots 4)</tex> и <tex>[4 \ldots 5)</tex>.
==Реализация==
Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией. Пусть в узлах дерева хранятся структуры из трех полей:* <codetex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале. '''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://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://e-maxxrain.ifmo.ru/algocat/segment_tree view.php/vis/trees/segment- MAXimal :: algo :2006 Дискретная математика: Дерево Алгоритмы — Визуализатор дерева отрезков]
[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 - Дерево отрезков — Википедия]]
