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