Изменения

Будем рассматривать запрос на примере задачи 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> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины). Для текущего состояния проверяем следующие условия: * Если запрашиваемый отрезок текущий полуинтервал не пересекается с рассматриваемым отрезкомискомым, то возвращаем нейтральный элемент.:''Например'': текущий <tex>[1 \ldots 3)</tex>, а искомый <tex>[3 \ldots 5)</tex>; * Если запрашиваемый отразив совпадает с запрашиваемыйтекущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.Иначе считаем для подотрезков рекурсивно:''Например'': текущий <tex>[2 \ldots 3)</tex>, комбинируем ответ и возвращаем значение.а искомый <tex>[2 \ldots 4)</tex>;

Рассмотрим работу программы данный алгоритм на дереве отрезков для элементов [1 примере задачи <tex>\mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на отрезке). При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях. 8]. Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма {{- --}} это отрезок <tex>[1 \ldots 4]</tex> (полуинтервал <tex>[2 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>

4Таким образом ответ на полуинтервале <tex>[1 \ldots 5)лист 6 не пересекается с отрезком </tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2 .. 5] =)</tex> возвращаем нулевое значение, лист 5 целиков внутри <tex>[2 .. \ldots 4)</tex> и <tex>[4 \ldots 5] =)</tex> возвращаем значение в листе 5.

Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией. Пусть в узлах дерева хранятся структуры из трех полей:* <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] не пересекается с [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>[[Дерево отрезков. Построение]]

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