Lazy Propagation

A segment tree that supports range updates as well as range queries, in $O(\log n)$ each, by deferring updates until they are needed.

The idea

When a range update fully covers a node’s range, apply it to that node’s aggregate and store a pending tag instead of recursing into the children. Push the tag down only when a later operation needs to enter a child.

Implementation — range add, range sum

struct LazySeg {
    int n;
    vector<long long> t, lz;
 
    LazySeg(int n) : n(n), t(4*n, 0), lz(4*n, 0) {}
 
    void apply(int node, int l, int r, long long v) {
        t[node] += v * (r - l + 1);
        lz[node] += v;
    }
    void push(int node, int l, int r) {
        if (!lz[node]) return;
        int m = (l + r) / 2;
        apply(2*node,   l,   m, lz[node]);
        apply(2*node+1, m+1, r, lz[node]);
        lz[node] = 0;
    }
    void update(int node, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(node, l, r, v); return; }
        push(node, l, r);
        int m = (l + r) / 2;
        update(2*node, l, m, ql, qr, v);
        update(2*node+1, m+1, r, ql, qr, v);
        t[node] = t[2*node] + t[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 t[node];
        push(node, l, r);
        int m = (l + r) / 2;
        return query(2*node, l, m, ql, qr) + query(2*node+1, m+1, r, ql, qr);
    }
};

Three places must be right: apply (how a tag changes an aggregate), push (how a tag reaches children), and pulling up (t[node] = combine(children)) after recursing.

The two rules for a valid lazy tag

1. A tag must be applicable to a whole node in $O(1)$, using only the node’s range length and current aggregate.
2. Tags must compose. Two pending updates on the same node must merge into one tag.

If either fails, lazy propagation does not work for that operation — see Segment Tree Beats for a technique that handles some of the cases where rule 1 breaks.

Common tag types

Update	Query	Tag	Apply
range add	range sum	add	t += add * len
range add	range min/max	add	t += add
range assign	range sum	set (with a “has value” flag)	t = set * len
range assign	range min/max	set	t = set
range multiply + add	range sum	(mul, add) pair	t = t*mul + add*len
range flip (0/1)	count of ones	flip boolean	t = len - t
range add	max prefix sum	add	needs a richer node

Composing assign and add

The classic tricky combination. Represent every pending update as an affine map $x\mapsto \mathrm{mul}\cdot x+\mathrm{add}$; composing two such maps is another affine map:

$(m_2,a_2)\circ (m_1,a_1)=(m_1{m}_2,a_1{m}_2+a_2).$

An assign to $v$ is $(0,v)$; an add of $d$ is $(1,d)$. This single representation handles all four combinations correctly, and is worth writing once and keeping in a template.

Order matters

When composing, apply the existing tag first and the new tag second (or the other way — but be consistent, and match push). Getting the order backwards produces answers that are right on simple tests and wrong on interleaved updates. Test with a brute force.

What lives in a node

Richer nodes solve richer problems, as long as the merge is associative:

Node stores	Answers
sum	range sum
min, count of min	range min and how many
max prefix / suffix / total / best	maximum subarray sum in a range
gcd of differences + first element	range gcd with range add
sorted list of elements	merge sort tree queries
a convex hull of lines	Li Chao-style queries

Alternatives

• Range update, point query only → a BIT on the difference array is far simpler.
• Range add, range sum → two BITs is shorter and faster than a lazy segment tree.
• All updates before all queries → a plain difference array, $O(n+q)$.
• Range assign only, no other update → “Chtholly tree” (an interval map in a std::map) is $O(n\log n)$ amortized on random data and much simpler.

See also: Segment Tree · Segment Tree Beats · Fenwick Tree