Chapter 99

Home

Refactoring: Lazy Propagation

Point updates are O(log N). But updating every element in a range one-by-one is O(N log N). Lazy propagation delays range updates — mark a node as "needs update" and push only when needed. O(log N) per range update.

Before: Range Update via Point Updates

C++ — O(N log N) naive range update

for (int i = l; i <= r; i++) seg.update(i, val);  // O(N log N)

After: Lazy Propagation (Range Add, Range Sum)

C++ — lazy segment tree

struct LazySegTree {
    vector tree, lazy;
    int n;

    LazySegTree(int sz) {
        n = sz;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void push(int node, int l, int r) {
        if (lazy[node] == 0) return;
        tree[node] += lazy[node] * (r - l + 1);
        if (l != r) {  // not leaf
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void range_add(int ql, int qr, long long val,
                   int node, int l, int r) {
        push(node, l, r);
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            lazy[node] += val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        range_add(ql, qr, val, node * 2, l, mid);
        range_add(ql, qr, val, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long range_sum(int ql, int qr, int node, int l, int r) {
        push(node, l, r);
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return range_sum(ql, qr, node * 2, l, mid)
             + range_sum(ql, qr, node * 2 + 1, mid + 1, r);
    }
};

// Range add: O(log N). Range sum: O(log N).

Key Takeaways