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

Пока менялся один элемент, всё было просто. Теперь меняется целый отрезок: прибавить $d$ ко всем элементам с $l$-го по $r$-й.

Менять по одному — $O(n)$ на запрос. Но отрезок изменения, как и отрезок запроса, разбивается на $O(\log n)$ узлов. Значит можно пометить эти узлы и не спускаться дальше.

Что означает пометка

Пометка на узле означает: «ко всему моему отрезку это применено, но детям я ещё не сказал».

Отсюда два обязательных правила.

1. Значение узла всегда актуально. Пометка ставится вместе с пересчётом значения, а не после.
2. Перед спуском в детей пометка проталкивается. Функция push передаёт её обоим детям и снимает с себя.

void apply(int v, int tl, int tr, long long d) {
    sum[v] += d * (tr - tl + 1);      // для суммы длина важна
    add[v] += d;
}

void push(int v, int tl, int tr) {
    if (add[v] == 0) return;
    int tm = (tl + tr) / 2;
    apply(2 * v, tl, tm, add[v]);
    apply(2 * v + 1, tm + 1, tr, add[v]);
    add[v] = 0;
}

Проталкивать надо в каждой функции, которая спускается: и в изменении, и в запросе. Забытый push в запросе — самая частая ошибка темы, и ловится она не глазами, а тестом, где изменение на большом отрезке идёт перед запросом внутрь него.

Длина отрезка

Для суммы применение пометки умножается на длину отрезка, для минимума и максимума — нет: сдвиг всех элементов на $d$ сдвигает и минимум на $d$.

Перепутать эти два случая легко, а проявляется ошибка только на отрезках длины больше единицы.

Когда проталкивать не нужно

Если пометка коммутирует с операцией узла, push можно не писать вовсе. Прибавление коммутирует с минимумом и максимумом: прибавить ко всем и взять минимум — то же, что взять минимум и прибавить.

Тогда значение узла хранит ответ с учётом пометок внутри поддерева, а пометки предков добавляются по дороге:

void update(int v, int tl, int tr, int l, int r, long long d) {
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) { tree[v] += d; add[v] += d; return; }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, d);
    update(2 * v + 1, tm + 1, tr, l, r, d);
    tree[v] = std::min(tree[2 * v], tree[2 * v + 1]) + add[v];
}

long long query(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return INF;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return std::min(query(2 * v, tl, tm, l, r),
                    query(2 * v + 1, tm + 1, tr, l, r)) + add[v];
}

Ключевые места — последние строки обеих функций: свою пометку надо прибавить. Забыть в update — ответы поедут после нескольких прибавлений, забыть в query — сразу.

Схема короче и быстрее, но работает только для коммутирующих пометок. Присвоение к ним не относится — про это следующая статья.