Отложенные операции

Очень часто при решении задач на [дерево отрезков], [декартово дерево], корневую декомпозицию требуется применять операцию изменения не к одному элементу массива, а к подотрезку. Замечание. Считается, что мы умеем применять эту операцию к одному элементу массива, и что мы умеем применять ее "по частям" (к разным подотрезкам массива по очереди).

Push-величины

Применим следующий трюк: если нам нужно обновить значение подотрезка, то мы отложим эту операцию ~~до востребования~~. Запомним в соответствующих вершине/блоке, что мы должны в будущем сделать обновление в потомков. Если нам вдруг понадобится значение, лежащее в вершине/блоке, то мы посчитаем его так, как будто мы обновили отрезок, а напоминание о том, что надо сделать со всеми элементами, мы "протолкнем" в потомков (отсюда и название push).

Реализация

Приведем тут несколько мыслей и реализацию для дерева отрезков.

Вызывать push надо каждый раз, когда мы обращаемся к вершине, если между обращениями к ней могло примениться обновление
push-пометки надо не забывать очищать
если мы снимаем push-пометку с единичного элемента, то мы про нее можем забыть

Вот тут будет код

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s