1632
правки
Изменения
м
==Описание==Данная рекурсивная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.
Рассмотрим данный алгоритм на примере задачи RSQ''Замечание.''Используем в алгоритме не отрезки, а полуинтервалы (запрос суммы на отрезкелевая граница включительно, а правая {{---}} нет), то есть пусть есть уже построенное дерево отрезков и задача найти сумму на отрезке <tex>[a .. b]</tex>.[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]
Будем передавать в качестве параметров рекурсий следующие переменные:* <tex>ver</tex> {{---}} номер(в массиве с деревом Пусть есть уже [[Дерево отрезков) текущей вершины дерева.* <tex>l</tex>, <tex>r</tex> {{---}} левая Построение|построенное дерево отрезков]] и правая границы отрезков, за которые "отвечает" наша вершина.* идет запрос на полуинтервале <tex>[a</tex>, <tex>\ldots b)</tex> {{---}} левая и правая границы запрашиваемого отрезка.
Запустим рекурсивную процедуру от всего отрезкаВ качестве параметров рекурсий передаем следующие переменные:* <tex>node</tex> {{---}} номер (то есть от корневой в массиве с деревом отрезков) текущей вершины)дерева.* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.
Для текущего состояния проверяем следующие условия :Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
* Если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.''Например''Для текущего состояния проверяем следующие условия: текущий <tex>[1..2]</tex>, а искомый <tex>[3 .. 4]</tex>;
[[Файл:Шагал1538.JPG|right|380px|thumb|Дерево отрезков]]
*Текущий отрезок <tex>[1 .. 8]</tex>, он больше <tex>[2 .. 5]</tex> => переходим по рекурсивным вызовам на <tex>[1 .. 4]</tex> и <tex>[5 .. 8]</tex>
*<tex>[1 .. 4]</tex> выходит за границы<tex> [2 .. 5]</tex>, <tex>[5 .. 8]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим по рекурсивным вызовам на <tex>[1 .. 2]</tex>, <tex>[3 .. 4]</tex> и <tex>[5 .. 6]</tex>, <tex>[7 .. 8]</tex>.
*<tex>[1 .. 2]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим в листья 1, 2; <tex>[3 .. 4]</tex> целиком внутри <tex>[2 .. 5]</tex> => возвращаем значение в <tex>[3 .. 4]</tex>;
<tex>[7 .. 8]</tex> не пересекается с <tex>[2 .. 5]</tex> => возвращаем нулевое значение, <tex>[5 .. 6]</tex> выходит за границы <tex>[2 .. 5]</tex> => переходим к листьям 5 и 6
*лист 6 не пересекается с отрезком Таким образом ответ на полуинтервале <tex>[2 .. 1 \ldots 5])</tex> =равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2)</tex> возвращаем нулевое значение, лист 5 целиков внутри <tex>[2 .. 5]\ldots 4)</tex> =и <tex> возвращаем значение в листе [4 \ldots 5)</tex>.
<code>Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.
int get_sum (int ver, int l, int r, int a, int b)Пусть в узлах дерева хранятся структуры из трех полей: { if ([l,r] * <tex>\bigcapmathtt{left}</tex> [a{{---}} левая граница полуинтервала, b] = за который "отвечает" текущая вершина.* <tex> \varnothingmathtt{right}</tex>) return 0; if ([l,r] = [a, b]){{---}} правая граница этого полуинтервала. return tree[ver]; int m = (l + r) / 2; return get_sum (ver * 2, l, m, a, min(b, m)) + get_sum (ver * 2 + 1, m + 1, r, max(a, m + 1), b); <tex> \mathtt{res} </codetex>{{---}} результат операции на полуинтервале.
rollbackEdits.php mass rollback
==Алгоритм==
* Текущий отрезок совпадаетЕсли текущий полуинтервал не пересекается с искомым, то возвращаем значение в текущей вершиненейтральный элемент.:''Например'': текущий и <tex>[1 \ldots 3)</tex>, а искомый <tex>[2..3]\ldots 5)</tex>;
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.:''Например'': текущий <tex>[2 \ldots 3)</tex>, а искомый <tex>[2 \ldots 4)</tex>; * Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом сумма возвращаем значение на текущем отрезке равна сумме полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов функцийвыполнения на детях. Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, запущенных от детейто операция выполняется за <tex>O(\log n)</tex>.
==Пример==
Рассмотрим работу программы данный алгоритм на дереве отрезков для элементов примере задачи <tex>[1 \mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на отрезке). При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях. Пусть дерево содержит <tex>8]</tex>.Пусть листьев и запрашиваемая сумма {{--- }} это отрезок <tex>[2 1 \ldots 4]</tex> (полуинтервал <tex>[1 \ldots 5)</tex>).[[Файл:Image_4. 5png|right|602px|Пример раб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> возвращаем нулевое значение
* На глубине <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> возвращаем нейтральное значение
==Реализация==
'''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 - Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]