69
правок
Изменения
→Реализация
==Реализация==
Рассмотрим реализацию задачи RSQ о дереве отрезков с произвольной ассоциативной бинарной операцией.
Пусть в узлах дерева хранятся структуры из трех полей:
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
* <tex> sumres</tex> {{---}} сумма на полуинтервале.
<code>
'''int''' get_sum 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''' 0neutral
'''if''' [l, r) <tex>\subset</tex> [a, b)
'''return''' tree[node].sumres '''return''' get_sum query (node * 2 + 1, a, b) + get_sum query (node * 2 + 2, a, b)
</code>
