v. Lazy Propagation

Range updates in $O (lo g n)$ : when an update covers a whole node, apply it to the node’s summary and leave a tag for the children, pushing it down only when a later operation enters the node. This works iff:

a tag can update a node’s summary in $O (1)$ from the summary alone (plus things like the length, which you store in the node);
tags compose: two pending updates merge into one tag.

When rule 1 fails, look at segment tree beats or sqrt decomposition.

Generic lazy segment tree

// S: node summary, F: tag. op(S,S), e(), mapping(F,S) -> S, composition(F new, F old) -> F, id()
template<class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct LazySegTree {
    int n, size, lg; vector<S> d; vector<F> lz;
    LazySegTree(const vector<S>& a) : n(sz(a)) {
        lg = 0; while ((1 << lg) < n) lg++; size = 1 << lg;
        d.assign(2 * size, e()); lz.assign(size, id());
        copy(all(a), d.begin() + size);
        for (int i = size - 1; i > 0; i--) pull(i);
    }
    void pull(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void apply1(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); }
    void push(int k) { apply1(2 * k, lz[k]); apply1(2 * k + 1, lz[k]); lz[k] = id(); }
    S prod(int l, int r) {                               // [l, r)
        if (l == r) return e();
        l += size; r += size;
        for (int i = lg; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sl = e(), sr = e();
        for (; l < r; l >>= 1, r >>= 1) { if (l & 1) sl = op(sl, d[l++]); if (r & 1) sr = op(d[--r], sr); }
        return op(sl, sr);
    }
    void apply(int l, int r, F f) {                      // [l, r)
        if (l == r) return;
        l += size; r += size;
        for (int i = lg; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        for (int a = l, b = r; a < b; a >>= 1, b >>= 1) { if (a & 1) apply1(a++, f); if (b & 1) apply1(--b, f); }
        for (int i = 1; i <= lg; i++) {
            if (((l >> i) << i) != l) pull(l >> i);
            if (((r >> i) << i) != r) pull((r - 1) >> i);
        }
    }
};

This is the AtCoder Library design: iterative, about 2x faster than recursive, and every problem is “define S, F, and the five functions”. Descents (maxRight, minLeft) extend the same way as in the plain tree (push on the way down).

Proof: lazy propagation is correct

Invariant. At all times, for every node $k$ : d[k] equals the true aggregate of its range as if every tag ever applied to $k$ or an ancestor of $k$ that hasn’t yet been pushed past $k$ has already been folded in — and every tag still sitting in lz[k] is exactly the composition of pending updates that are reflected in d[k] but not yet reflected in $k$ ‘s children. This holds initially (no tags, d built bottom-up from the raw array) and is preserved by every operation:

apply1(k, f) updates d[k] = mapping(f, d[k]) (rule 1: a tag maps a summary to the new summary in $O (1)$ ) and, if $k$ is internal, composes $f$ into lz[k] via composition(f, lz[k]) — the required semantics “apply the old pending tag first, then the new one” (rule 2), so lz[k] always correctly represents “what still needs to reach the children to match d[k]”.

push(k) calls apply1 on both children with lz[k], making their d and lz reflect that pending tag too (maintaining the invariant one level down), then clears lz[k] — correct because after this, $k$ has no pending work left to distribute, matching lz[k]=id().

prod/apply push every ancestor of the boundary nodes $l, r$ top-down before touching them (the for (i = lg; i >= 1; i--) loops), which guarantees that by the time the algorithm reads or writes a node in the canonical decomposition, every tag above it has already been pushed down into it — so its d value is the true, fully up-to-date aggregate, not a stale one hidden behind an ancestor’s unpushed tag. apply then pulls every touched ancestor bottom-up after (for (i = 1; i <= lg; i++)), re-deriving each from its (now correct) children — necessary because applying a tag only to the canonical-decomposition nodes leaves their ancestors stale otherwise.

Composition order matters: since mapping and composition must jointly satisfy $mapping (g, mapping (f, s)) = mapping (composition (g, f), s)$ for the merged tag to produce the same result as applying $f$ then $g$ separately, and the two orders $(g, f)$ vs $(f, g)$ generally disagree for non-commuting updates (e.g. affine maps), composition(new, old) must consistently mean “old was applied first” to match the chronological order updates actually happened in.
Given these invariants, prod(l,r) folds the canonical decomposition of $[l, r)$ exactly as in the proof for the plain bottom-up tree, now over fully pushed, up-to-date nodes. $■$

Tested against a direct $O (n)$ array simulation of range-add/range-sum over random interleaved apply/prod calls — all match.

Common tag algebras

Update	Query	`S`	`F` and mapping
add	sum	(sum, len)	$x$ : sum $+ = x \cdot$ len
add	min/max	value	$x$ : value $+ = x$
assign	sum	(sum, len)	optional value: sum $= v \cdot$ len
affine $x \to b x + c$	sum mod $p$	(sum, len)	$(b, c)$ : sum $= b \cdot$ sum $+ c \cdot$ len; compose $(b_{2}, c_{2}) \circ (b_{1}, c_{1}) = (b_{1} b_{2}, b_{2} c_{1} + c_{2})$
assign + add	anything		encode assign $v$ as $(0, v)$ and add $d$ as $(1, d)$ in the affine algebra
flip bits (0/1)	count ones	(ones, len)	flip: ones $=$ len $-$ ones
add arithmetic progression $a + d \cdot j$	sum	(sum, len)	$(a, d)$ ; the right child receives $(a + d \cdot len_{L}, d)$ ; tags add up
range XOR with $x$ , query sum	per-bit counts (ones per bit, len)	$x$ : flip counts of bits set in $x$
assign, query “number of distinct runs”	(runs, left value, right value)	assign: runs = 1
range assign, query max subarray sum	(sum, pre, suf, best, len)	assign $v$ : everything becomes a function of $v$ and len
range add, query max subarray sum		not expressible as a lazy tag: use sqrt decomposition with per-block convex hulls (KTT, kinetic segment tree)
range sort ascending/descending		not lazy: sortable segment tree (Merging)

Order of composition: composition(new, old) means “apply old first, then new”. Get it backwards and simple tests pass while interleaved updates fail. Test against a brute force with random interleaving.

Proof: the affine tag algebra for assign+add

Representing a pending map as $(b, c) : x \mapsto b x + c$ , applying $(b_{1}, c_{1})$ then $(b_{2}, c_{2})$ gives $x \mapsto b_{2} (b_{1} x + c_{1}) + c_{2} = (b_{2} b_{1}) x + (b_{2} c_{1} + c_{2})$ , which is itself affine with coefficients $(b_{1} b_{2}, b_{2} c_{1} + c_{2})$ — so affine maps are closed under composition, confirming the table’s $(b_{2}, c_{2}) \circ (b_{1}, c_{1}) = (b_{1} b_{2}, b_{2} c_{1} + c_{2})$ . An assign to $v$ is the constant map $x \mapsto 0 \cdot x + v$ , i.e. $(0, v)$ ; an add of $d$ is $x \mapsto 1 \cdot x + d$ , i.e. $(1, d)$ . Both are affine, so both compose correctly under the single formula above — in particular assign-then-add gives $(1, d) \circ (0, v) = (0, 1 \cdot v + d) = (0, v + d)$ (correctly: assign $v$ then add $d$ is “assign $v + d$ ”), and add-then-assign gives $(0, v) \circ (1, d) = (0, v)$ (correctly: anything followed by an assign just becomes that assign, discarding the add). $■$

Tag permanence (no push-down)

For commutative tags (adds), keep each tag on the node forever and add its effect while descending during queries. Queries never modify the tree, which is exactly what persistent and dynamic trees need (no node copies on query), and what makes 2D “segment tree of segment trees” range add possible for sums.

// add v on [x, y) inside node p covering [l, r): sum[p] += v * overlap; if fully covered: tag[p] += v; else recurse
// query: if fully covered return sum[p]; else tag[p] * overlap + children

Recurring problems

Range add, range min with “count of minimum”: count zeros after adds (cover length of rectangles in sweeps: min $= 0$ means uncovered).
Range assign, range sum with $1 0^{9}$ coordinates: dynamic lazy tree or compress coordinates.
“Paint” problems: assign with colour, query count of a colour in range: per-node “uniform colour or mixed”, recurse into mixed nodes; amortized like Chtholly.
Range $a_{i} \to a_{i} mod x$ , $⌊ a_{i} / x ⌋$ , $a_{i}$ : not lazy; recurse while the node’s max shows the update matters. Each element changes $O (lo g a)$ times (mod: when it changes, it at least halves), so the total is amortized $O ((n + q) lo g n lo g A)$ (Beats).
Range add, range gcd: store the gcd of the difference array in a plain segment tree plus a Fenwick for values: $g cd (a_{l} .. a_{r}) = g cd (a_{l}, g cd (d_{l + 1} .. d_{r}))$ , and a range add changes only two differences.

Alternatives that are shorter

Situation	Tool
range add, point query	Fenwick on the difference array
range add, range sum	two Fenwicks
all updates before all queries	difference array
range assign only, random data	Chtholly tree

whoashish's cp notes

Directory

v. Lazy Propagation

Generic lazy segment tree

Common tag algebras

Tag permanence (no push-down)

Recurring problems

Alternatives that are shorter

Graph View

Table of Contents