Изменения

Будем рассматривать ''Замечание.''Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет). Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a \ldots b)</tex>. В качестве параметров рекурсий передаем следующие переменные:* <tex>node</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>\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>).[[Файл:123Image_4.jpgpng|right|380px|thumb602px|Пример дерева отрезков для вычисления суммраб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> возвращаем нейтральное значение суммы  Таким образом ответ на этом отрезкеполуинтервале <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)

int sum (int v, int tl, int tr, int l, int r) { if (l > r) 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>[[Дерево отрезков. Построение]]

==СсылкиИсточники информации==* [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 - Дерево отрезков — Википедия]]