286
правок
Изменения
Нет описания правки
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]
Рассмотрим данный алгоритм на определенных глубинах рекурсии (, то есть на разных уровнях дерева(на рисунке глубина обозначена слева от уровня):
* На глубине <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), [1.. 2), [4.. 5), [5 .. 6) </tex>
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение
* На глубине <tex>3</tex>.
** Листья <tex>[1.. 2), [4.. 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них** Листья <tex>[0.. 1), [5.. 6)</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое нейтральное значение
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
* <tex> res</tex> {{---}} результат операции на полуинтервале.
'''int''' query('''int''' node, '''int''' a, '''int''' b)
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
