69
правок
Изменения
Нет описания правки
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):
* На глубине <tex>0</tex>. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>
* На глубине <tex>1</tex>. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex>
* На глубине <tex>2</tex>.
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex>
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
* На глубине <tex>3</tex>.
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)
</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://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
