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