Изменения
Лишний пробел
==Алгоритм==
''Замечание.''
Используем в алгоритме не отрезки, а полуинтервалы(левая граница включительно, а правая {{- --}} нет).
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. \ldots b)</tex>.[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков]]
В качестве параметров рекурсий передаем следующие переменные:
* <tex>node</tex> {{---}} номер(в массиве с деревом отрезков) текущей вершины дерева.
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершинвершина.Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
* Если текущий полуинтервал не пересекается с искомымлежит внутри запрашиваемого полуинтервала, то возвращаем некоторое значение, которое не повлияет на результат запроса на запрашиваемом полуинтервалев текущей вершине.:''Например'': текущий <tex>[1..2 \ldots 3)</tex>, а искомый <tex>[3 .. 52 \ldots 4)</tex>;
* Если текущий полуинтервал совпадает, то Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение в текущей вершинена текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.''Например'': текущий и искомый <tex>[2..4)</tex>;
При этом сумма на текущем полуинтервале(в случае вызова рекурсий от детей) равна сумме результатов выполнения операций операции на этих детях.
Пусть дерево содержит <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о дереве отрезков с произвольной ассоциативной бинарной операцией.<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 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]