333
правки
Изменения
→Несогласованные поддеревья
Сперва рассмотрим так называемые '''несогласованные поддеревья'''.
Пусть дерево отрезков хранит в вершинах результат выполнение операций выполнения операции <tex>\oplus</tex> на текущем отрезке, а запрос обновления идет по операций операции <tex>\odot</tex>.
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации операция <tex>\odot</tex> должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:
