Отложенные обновления: менять целый диапазон за логарифм

Если ты понимаешь, зачем нужны отложенные метки, как обновление диапазона помечает O(log n) узлов вместо спуска к листьям и как метка проталкивается детям при следующем заходе, листай до «Теперь сам».

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

Обновить один элемент дерево отрезков умеет за O(log n). Но «прибавь 5 ко всем с l по r» - это r − l + 1 элементов; сделать по одному - O(n) на операцию, и весь выигрыш дерева пропал. Заметь: запрос суммы на [l, r] мы БЕРЁМ из O(log n) крупных узлов, целиком лежащих внутри диапазона, - не спускаясь к листьям. Хочется так же и ОБНОВЛЯТЬ: дойдя до узла, целиком накрытого диапазоном, изменить его «оптом», не трогая детей. Но свёртки детей тогда станут неверными... если только не ЗАПОМНИТЬ в узле, что «всем ниже причитается прибавка 5», и разобраться с детьми ПОТОМ - лишь если туда кто-то полезет. Отложить работу до востребования - вот идея lazy propagation.

На что это похоже

Начальник получил распоряжение «повысить зарплату всему департаменту на 5%». Он не бежит к каждому из тысячи сотрудников лично. Он вешает на дверь департамента ПРИКАЗ «+5% всем» и сразу правит СУММАРНЫЙ бюджет департамента в своей отчётности. А до конкретных отделов приказ доводят, только когда в отдел реально приходит проверка или запрос по конкретному сотруднику - тогда приказ «спускают» на отделы (и они вешают его уже у себя), потом на людей. Пока никто не спрашивает - приказ просто висит на двери, а работа не делается. Отложенная метка в дереве отрезков - такой приказ на двери: изменение записано наверху, а вниз доводится лишь по требованию.

Механизм: ленивая метка и push down

К каждому узлу добавляем поле lazy - «отложенное изменение для всего поддерева» (для сложения - сколько ещё прибавить каждому элементу ниже). Две вещи:

обновить_диапазон(узел [lo,hi], l, r, delta):
    если [lo,hi] ВНЕ [l,r]:            выход
    если [lo,hi] ЦЕЛИКОМ внутри [l,r]:
        свёртка узла += delta * (hi − lo + 1)   # поправить сумму узла оптом
        lazy[узел]  += delta                    # запомнить «детям причитается delta»
        выход                                    # к детям НЕ спускаемся!
    иначе:
        push_down(узел)                          # сначала спустить накопленное детям
        обновить(лево); обновить(право)
        свёртка узла = свёртка(лево) + свёртка(право)

push_down(узел):   # протолкнуть отложенное детям (лениво, при заходе)
    если lazy[узел] != 0:
        применить lazy[узел] к обоим детям (их свёрткам и их lazy)
        lazy[узел] = 0

Ключевое: обновление диапазона, как и запрос, тормозит на узлах, ЦЕЛИКОМ лежащих внутри [l, r] - их O(log n), - и лишь помечает их, не спускаясь к листьям. А push_down доводит метку до детей ТОЛЬКО когда запрос или другое обновление реально входит в это поддерево. Запрос суммы теперь тоже обязан делать push_down при спуске - иначе прочитает устаревшие свёртки детей. Итог: и запрос, и обновление ДИАПАЗОНА - O(log n).

Правило

Отложенные обновления (lazy propagation) дают дереву отрезков обновление ЦЕЛОГО ДИАПАЗОНА за O(log n) вместо O(n). Когда обновление накрывает узел ЦЕЛИКОМ, его свёртку правят оптом (delta · длину) и вешают ленивую метку lazy, НЕ спускаясь к детям. Метка ПРОТАЛКИВАЕТСЯ детям (push_down) лишь тогда, когда следующая операция реально входит в это поддерево. И запрос, и обновление обязаны делать push_down при спуске. Обновление диапазона задевает те же O(log n) узлов, что и запрос. Работа откладывается до момента, когда она действительно нужна.

Разбор: почему откладывание не теряет и не портит данные

Тревога законна: мы «недоделали» работу (не спустили изменение к листьям) - не всплывёт ли где неверная сумма? Нет, и вот инвариант, который это гарантирует: свёртка САМОГО узла корректна всегда (она уже учитывает его собственную метку), а метка lazy означает «изменение уже учтено в моей свёртке, но ЕЩЁ НЕ передано детям». Пока никто не заходит к детям, их устаревшие свёртки НИКТО НЕ ЧИТАЕТ - значит их неверность безвредна. А как только операция спускается в поддерево, первым делом вызывается push_down: он применяет метку к свёрткам детей и к их собственным lazy (накапливая, если у ребёнка уже была метка), обнуляя метку родителя. К моменту, когда мы РЕАЛЬНО читаем свёртку ребёнка, она уже верна. То есть данные не портятся - откладывается лишь распространение, а не сам эффект: эффект мгновенно отражён в свёртке узла, а его «разноска» вниз происходит ровно тогда и только тогда, когда вниз кто-то идёт. Ленивость безопасна, потому что неверные значения существуют только там, куда никто не смотрит.

Разбор: почему это та же амортизация «работа по требованию»

Отложенные обновления - конкретный случай общего принципа «не делай работу, пока её не спросили», который ты уже видел. Растущий массив не копирует заранее - только при переполнении. Splay-дерево не балансирует по правилу - выправляется при обращении. Здесь дерево не разносит изменение по всем элементам сразу - откладывает до захода в поддерево. Общая выгода: если в помеченное поддерево так никто и не зайдёт, разноска НЕ СЛУЧИТСЯ вовсе - работа сэкономлена целиком. А если зайдёт - push_down делает ровно один уровень разноски за O(1), и суммарно по любому пути это O(log n). Ленивость превращает «обновить O(n) элементов» в «пометить O(log n) узлов + разносить по мере надобности». Это фундаментальный приём проектирования: откладывать дорогую работу до момента, когда без неё уже не обойтись, - и часто она не понадобится. Тот же образ мысли даёт кеши, копирование- при-записи (copy-on-write), ленивые вычисления в языках программирования.

Что ломается без этого

Первая ошибка - обновлять диапазон, спускаясь к каждому листу: это O(n) на операцию, бессмысленно иметь дерево. Ленивая метка на целиком накрытых узлах - обязательна. Вторая - забыть push_down в ЗАПРОСЕ (делать его только в обновлении): запрос спустится к детям с устаревшими свёртками и вернёт неверную сумму. И запрос, и обновление проталкивают метку при спуске. Третья - неправильно КОМБИНИРОВАТЬ метки: если у ребёнка уже висит метка, новая должна с ней СЛОЖИТЬСЯ (для сложения) или скомпоноваться (для присваивания порядок важен) - просто перезаписать нельзя, иначе потеряешь прежнее изменение. Четвёртая - забыть, что метку надо применять И к свёртке узла (сразу, оптом), И к его lazy (для будущей разноски) - применишь только к одному, и данные разъедутся.

Зачем это в работе

Отложенные обновления делают дерево отрезков по-настоящему мощным: теперь оно умеет и запрос по диапазону, и обновление по диапазону - оба за O(log n). Это нужно везде, где массово меняют и опрашивают диапазоны: «прибавить/присвоить значение на отрезке» и «сумма/мин/макс на отрезке» вперемешку - в системах бронирования (занять диапазон дат), в редакторах и таблицах (форматировать диапазон ячеек), в геометрии (сканирующая прямая с накоплением), в олимпиадных задачах про диапазонные операции. Понимать lazy propagation - значит владеть полным деревом отрезков (запрос и обновление диапазона) и, шире, усвоить принцип «ленивость»: откладывать распространение изменений до востребования, не портя корректность. Этот принцип - один из самых универсальных в программировании (кеши, copy-on-write, ленивые структуры), и дерево отрезков с отложенными метками - его чистый, наглядный пример. Так закрывается цель раздела: диапазонный запрос И диапазонное обновление за логарифм, а не за n.

Теперь сам

К дереву отрезков применили «+5 на диапазон [0, 3]», и узел, покрывающий ровно [0, 3], получил ленивую метку +5. Затем спросили сумму на [0, 1]. Что произойдёт с меткой и почему сумма получится верной, хотя листья ещё не обновлены?