Изменения

Для эффективной реализаций будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операций <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается так называемым "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операций <tex>\oplus</tex>, так как значение в детях могло измениться.

Таким образом необходимо А ответ же на запрос по операций <tex>\oplus</tex> реализуется почти так же, как и в случае без массовых обновлений. Отличие лишь в том, что следует во-первых не забыть раздать детям несогласованность, и во-вторых пересчитать свое значение.  Таким образом в обоих запросах очень важно протолкнуть детям несогласованность, вызвать функцию от детей и, в-третьихнаконец, пересчитать свое значение. Очень важно выполнить все три пунктав текущей вершине.