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

Рассмотрим такую модификацию задачи. Дан массив размера $n$, и требуется отвечать на запросы двух типов:

1. Заменить все значения на отрезке $[l, r)$ на $x$ (выполнить a[k] = x для всех $k$ от $l$ до $r$).
2. Вывести сумму элементов $a_i$ на отрезке с $l$ по $r$.

То есть теперь наш запрос обновления — это присвоение значения $x$ всем элементам некоторого отрезка $[l, r)$, а не только одному, и при этом мы всё ещё хотим обрабатывать оба запроса за $O(\log n)$.

#Основная идея

Мы не хотим спускаться до каждого элемента, где меняется сумма — их может быть очень много.

Вместо этого мы схитрим, и при запросе присваивания будем по возможности «помечать» некоторые вершины, что они и все их дети должны быть равны какому-то числу $d_v = x$, но спускаться дальше и непосредственно выполнять эти присвоения мы не будем.

Например, если пришел запрос «присвой число $x$ на всем массиве», то мы вообще фактических присвоений нигде делать не будем — только оставим пометку в корне дерева, что все элементы в нем равны $x$.

Когда нам позже понадобятся правильные значения таких вершин и их детей, то мы по пути от корня будем делать «проталкивание» информации из текущей вершины в её детей: если метка стоит, пересчитаем сумму текущего отрезка и передадим эту метку детям (не запускаясь рекурсивно от детей). Когда нам потом понадобятся поля детей, мы сделаем то же самое — пересчитаем в них сумму и передадим метку их детям, и так далее. Подобная операция будет гарантировать корректность данных в вершине ровно к тому моменту, когда они нам понадобятся.

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

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

#Реализация

Добавим поле-метку assign и создадим вспомогательную функцию push, которая будет производить проталкивание информации из этой вершины в обоих её сыновей.

struct Segtree {
    int lb, rb;
    int sum = 0, assign = -1; // "-1" означает, что присвоения делать не нужно
    Segtree *l = 0, *r = 0;
    
    Segtree(int lb, int rb) : lb(lb), rb(rb) {
        if (lb + 1 < rb) {
            int t = (lb + rb) / 2;
            l = new segtree(lb, t);
            r = new segtree(t, rb);
        }
    }
    
    void push() {
        if (assign != -1) {
            sum = (rb - lb) * assign;
            if (l) { // если дети есть
                l->assign = assign;
                r->assign = assign;
            }
        }
        assign = -1;
    }
};

Вызывать метод push стоит в самом начале обработки любого запроса — тогда он гарантирует, что в текущей вершине все значения корректны, а в сыновьях достаточно информации, чтобы при рекурсивном спуске и вызове push от них значения тоже стали корректными.

void add(int lq, int rq, int x) {
    push();
    if (lq <= lb && rb <= rq)
        assign = x;
    else if (l && max(lb, lq) < min(rb, rq)) {
        // если есть дети и отрезок запроса хоть как-то пересекается с нашим
        l->add(lq, rq, x);
        r->add(lq, rq, x);
        // ...дальше они сами разберутся
    }
}

int sum(int lq, int rq) {
    push();
    if (lb >= lq && rb <= rq)
        return s;
    if (max(lb, lq) >= min(rb, rq))
        return 0;
    return l->sum(lq, rq) + r->sum(lq, rq);
}

По-английски эта техника называется lazy propagation. Общая идея «давайте будем всё делать в последний момент» применима не только в дереве отрезков, но и в других структурах и в реальной жизни.