Изменения

[[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять так называемые '''массовые операцийоперации''', то есть данная структура позволяет выполнять операций операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>.

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

Рассмотрим в общем виде реализацию массовой операций операции на отрезке. Пусть необходимо отвечать запросы относительно операций операции <tex>\oplus</tex>, а запрос массового обновления идет по операций операции <tex>\odot</tex>.

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

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

Пусть поступают запросы двух типов {{---}} поиск элемента, соответствующего операций операции <tex>\oplus</tex>, и массовое обновление на отрезке относительно операций операции <tex>\odot</tex>. Используется классическая реализация дерева отрезка с полуинтервалами.

* <tex> ans</tex> {{---}} сумма на отрезке по операций операции <tex>\oplus</tex>.