1632
правки
Изменения
м
rollbackEdits.php mass rollback
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).
Для текущего состояния проверяем следующие условия :
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
==Пример==
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ }</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.
Пусть в узлах дерева хранятся структуры из трех полей:
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.
'''int''' query('''int''' node, '''int''' a, '''int''' b)
