Segment Tree with Lazy Propagation, in depth: the tag algebra, a node-by-node trace, tested affine updates and the composition-order bug

Why updates need to be lazy

Take two operations: add v to every element of a[l..r], and return the sum of a[l..r]. A query splits [l, r] into about 2 log2 n canonical nodes and adds their stored sums. An update covers the same canonical nodes, and the key observation is that for a node covering len elements, adding v to all of them raises its sum by exactly v times len. The node can update its own sum without knowing what its children hold.

It cannot update its descendants for free, so it does not. It records a pending operation, the tag, and promises to hand it down one level before anyone reads a descendant. Handing it down is a push; recomputing a parent from its children is a pull. Every correct lazy tree is a disciplined arrangement of those two operations, and every buggy one is missing one somewhere. Both operations become O(log n): for a million elements, about forty canonical nodes plus their ancestors.

The algebra behind every lazy tree

Lazy propagation needs three things: node values with an associative combine and an identity (a monoid, such as sums under addition), tags that also form a monoid under composition with a do-nothing identity, and a way to apply a tag to a node value that satisfies two laws.

• Distributes over combine. Applying tag f to the combination of two halves must equal combining f applied to each half. This is what lets a node apply f to its own summary instead of to every element.
• Respects composition. Applying g after f must equal applying the composed tag (g after f) once. This is what lets two pending tags merge into one, so a node never stores a queue of tags.

If either law fails, no careful coding produces a correct tree. Range add with range sum seems to break the first law, because adding v to three elements adds 3v to their sum. The fix is to make length part of the node value: store (sum, len) and apply add v as (sum + v times len, len). The AtCoder Library lazy segment tree is built exactly this way, and these terms are the fastest test of whether a new problem is lazy-propagation-shaped at all.

The affine row is the general case worth learning, because it contains the others: add v is (1, v), multiply by m is (m, 0) and assign v is (0, v). One correct affine tree answers all three update types, mixed in any order. The last row is the warning. Range chmin with range sum has no tag that tells a node its new sum without looking inside, so plain lazy propagation cannot do it; Segment Tree Beats adds bounded extra recursion to get around that.

A worked example, node by node

Use a = [3, 1, 4, 1, 5, 9, 2, 6], total 31; nodes are named by the interval they cover. First update: x becomes 2x on [2, 5], the affine tag (2, 0). The walk passes through the partly covered root and [0, 3], skips the disjoint [0, 1] and [6, 7], and stops at the fully covered [2, 3] and [4, 5]. Each applies (2, 0) to itself: sums 5 to 10 and 14 to 28, tags (2, 0). Pulls give [0, 3] = 14, [4, 7] = 36, root 50.

Second update: add 3 on [4, 7], tag (1, 3). [4, 7] is fully covered, so the walk stops there: sum 36 + 3 times 4 = 48, tag (1, 3), root 62. Nothing below [4, 7] knows about the +3, which is fine, because nothing has read it.

Now query a[3] + a[4]. The walk pushes [2, 3]'s (2, 0) to its leaves, so a[3] reads 2. On the right it pushes (1, 3) from [4, 7] to both children. For [4, 5] the new tag runs after the old one: (1, 3) after (2, 0) is (1 times 2, 1 times 0 + 3) = (2, 3), x becomes 2x + 3, and its sum becomes 28 + 3 times 2 = 34. Pushing (2, 3) to leaf 4 gives 2 times 5 + 3 = 13. The answer is 15, and the full array is [3, 1, 8, 2, 13, 21, 5, 9], sum 62, matching the root. These numbers are the output of the code below.

Tested implementation

This is a recursive implementation for affine updates and range sums modulo the prime 998244353. It was tested against a brute-force array on 300 random arrays of length 1 to 40 with 200 mixed add, multiply, assign and query operations each.

MOD = 998244353

class LazySegTree:
    """Range affine update x -> a*x + b, range sum query, all mod MOD."""

    def __init__(self, values):
        self.n = len(values)
        self.sum = [0] * (4 * self.n)
        self.mul = [1] * (4 * self.n)   # pending tag (a, b); identity is (1, 0)
        self.add = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, values)

    def _build(self, node, lo, hi, values):
        if lo == hi:
            self.sum[node] = values[lo] % MOD
            return
        mid = (lo + hi) // 2
        self._build(2 * node, lo, mid, values)
        self._build(2 * node + 1, mid + 1, hi, values)
        self.sum[node] = (self.sum[2 * node] + self.sum[2 * node + 1]) % MOD

    def _apply(self, node, length, a, b):
        # New tag runs AFTER the pending one: (a, b) o (a0, b0) = (a*a0, a*b0 + b)
        self.sum[node] = (a * self.sum[node] + b * length) % MOD
        self.mul[node] = a * self.mul[node] % MOD
        self.add[node] = (a * self.add[node] + b) % MOD

    def _push(self, node, lo, hi):
        a, b = self.mul[node], self.add[node]
        if a == 1 and b == 0:
            return
        mid = (lo + hi) // 2
        self._apply(2 * node, mid - lo + 1, a, b)
        self._apply(2 * node + 1, hi - mid, a, b)
        self.mul[node], self.add[node] = 1, 0

    def update(self, l, r, a, b, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            self._apply(node, hi - lo + 1, a, b)
            return
        self._push(node, lo, hi)                     # before descending
        mid = (lo + hi) // 2
        self.update(l, r, a, b, 2 * node, lo, mid)
        self.update(l, r, a, b, 2 * node + 1, mid + 1, hi)
        self.sum[node] = (self.sum[2 * node] + self.sum[2 * node + 1]) % MOD   # pull

    def query(self, l, r, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.sum[node]
        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        return (self.query(l, r, 2 * node, lo, mid)
                + self.query(l, r, 2 * node + 1, mid + 1, hi)) % MOD

# add v: update(l, r, 1, v)   multiply m: update(l, r, m, 0)   assign v: update(l, r, 0, v)

Two lines carry the technique: push before descending, in update and query, and pull after both recursive calls in update. A query needs no pull because it changes nothing a parent depends on.

Composition order: the bug small tests miss

Composition is where most lazy trees go wrong, quietly. Composed the other way round, old after new, [4, 5] in the example would get (2, 6), x becomes 2(x + 3), and leaf 4 would read 16 instead of 13. Tests that use one update kind pass, because add with add or multiply with multiply commutes. The bug appears only when two non-commuting tags meet on one node between pushes, which small hand tests rarely produce.

Two habits prevent it. Write the composition as a function commented new after old, derived once on paper by substituting one map into the other. And test against a brute-force oracle on random mixed operations over short arrays, which hits every node pairing many times. Encoding assign and add both as affine maps also removes the hand-rolled question of what assign-then-add means.

Variants

Iterative bottom-up trees. Leaves sit at positions n to 2n minus 1; pushes run explicitly from the root down to the boundary leaves before an operation and pulls back up afterwards. Faster by a constant factor, much harder to read; prefer a tested library version.

Non-commutative values. The combine must associate, not commute, so matrix products and string hashes work if the code always combines left then right.

Persistent lazy trees. A push must copy the children before writing tags into them, or an old version silently changes; see Persistent Segment Tree.

Avoiding a tree. If you only need range add with point queries, or range add with range sum and no other update kind, two Fenwick trees over a difference array do it in less code and memory; Range Updates and Point Queries derives that construction.

Failure modes

• Missing push in query. Queries that only hit fully covered nodes still pass, so the bug surfaces only on partial overlaps below a tagged node.
• Missing pull after update. The leaves are right and every ancestor is wrong; root sums disagree with the array.
• Tag applied without length. Range add on a sum tree must multiply by the child's length, which differs for the two children when the interval has odd size.
• Sentinel collisions. Storing assign as a value with 0 meaning none breaks the first time someone assigns 0. Use a separate flag, or the affine form whose identity is (1, 0).
• Overflow. In C++ or Java, a times sum plus b times len overflows 64 bits for large values; reduce modulo a prime or use 128-bit intermediates.
• Memory and speed. Three arrays of size 4n cost real memory at 10^7 elements; recursion depth is only about log2 n, but CPython is slow per node visit.

Using it in real systems

Lazy trees appear in booking systems that add load to time ranges and ask for the peak, and in analytics that correct ranges of time buckets. Keep a brute-force reference in CI with randomised differential tests, expose a debug method that pushes every tag to the leaves and compares with a fresh build, and log the operation sequence when a check fails so it can be replayed. Measure first: for a few thousand elements a flat array with vectorised range operations is often faster than any tree.

Trade-offs

What to do next

1. Run the class above against a brute-force list on random mixed operations; then deliberately swap the composition order and confirm your test catches it.
2. Re-derive the compose and apply rules for the table rows you need, writing each as a one-line function with its order in a comment.
3. Rewrite the node value as a (sum, len) pair so apply becomes a pure function, and adapt the code to range min with range add.
4. Compare with sqrt decomposition on your real sizes and keep the simpler structure if it is fast enough.
5. When a tag stops composing, as with chmin plus sum, move on to Segment Tree Beats rather than forcing it.