Segment Trees with Lazy Propagation, Clearly

Lazy propagation is one of those techniques that feels opaque until it suddenly clicks. This post aims for the click.

What Problem Does Lazy Solve?

A basic segment tree answers range queries in O(log n). But range updates — "add 5 to every element in [l, r]" — still take O(n) if you update each element individually.

Lazy propagation defers updates: instead of immediately pushing a range update down to every leaf, you store the pending update at the highest applicable node and only propagate it when you actually need the value below.

The Key Invariant

At every node, lazy[node] stores a pending update that has been applied to tree[node] but not yet to its children.

Before accessing children, you always call push_down(node).

A Range-Add, Range-Sum Template

struct SegTree {
    int n;
    vector<long long> tree, lazy;

    SegTree(int n) : n(n), tree(4*n, 0), lazy(4*n, 0) {}

    void build(vector<int>& a, int node, int l, int r) {
        if (l == r) { tree[node] = a[l]; return; }
        int mid = (l + r) / 2;
        build(a, 2*node, l, mid);
        build(a, 2*node+1, mid+1, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void push_down(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        // Apply to left child
        tree[2*node] += lazy[node] * (mid - l + 1);
        lazy[2*node] += lazy[node];
        // Apply to right child
        tree[2*node+1] += lazy[node] * (r - mid);
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }

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

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

    // Convenience wrappers (1-indexed)
    void update(int l, int r, long long val) { update(1, 1, n, l, r, val); }
    long long query(int l, int r) { return query(1, 1, n, l, r); }
};

Adapting to Other Operations

The template above does (range add, range sum). To change operations, you need to change two things:

1. How tree[node] is combined — sum → max/min/gcd
2. How lazy is applied — additive → multiplicative/assignment

For range-assign (set all elements in [l,r] to v), the push_down becomes:

tree[child] = lazy[node] * (child_size);
lazy[child] = lazy[node];  // overwrite, not accumulate

And you need a sentinel value (e.g. LLONG_MIN) to distinguish "no pending assignment" from "assign 0".

Common Mistakes

• Forgetting push_down before recursing — The most common bug. Always call push_down before touching children.
• Wrong size computation — Children span [l, mid] and [mid+1, r], sizes (mid - l + 1) and (r - mid).
• Using lazy before clearing — After pushing down, set lazy[node] = 0 (or sentinel).

Once you have a working template you trust, competitive programming gets noticeably easier. The hard part is the problem, not the data structure implementation.