Lazy propagation for range updates

Lazy propagation speeds up a segment tree's range updates. Instead of applying a change to every affected leaf right away, the change is recorded on one high-level node that already covers the whole updated range, and only pushed down to that node's children once they are actually visited by a later query or update.

Why defer the update

Applying a range update leaf by leaf costs time proportional to the size of the range. On an array of a million elements, updating half of it touches 500,000 leaves, and repeating that update many times makes the total work enormous.

Lazy propagation instead touches only the $O(\log n)$ internal nodes whose ranges exactly tile the updated range, and defers the leaf-level work until something actually needs those leaves. If updates cover large ranges but queries only ever touch small ones, most of that deferred work is never paid at all.

How the deferral works

Each node stores both its own summary value and a pending tag. When an update's range exactly covers a node's whole range, the tag is placed on that node and left there, without being applied to its children yet.

Think of the tag as a note attached to the node: "every descendant of this node still owes an increase of 5" or "every descendant still owes a multiplication by 2." The node itself already reflects the update in its own summary value, but its children do not know about it yet.

The moment a query or a later update needs to look inside that node, either directly or by descending past it, the tag is pushed down to its two children first. Each child absorbs its own copy of the tag into its summary, and if it has children of its own, keeps a copy of the tag as its own pending debt to pass down later. Only after this push does the query or update continue with values it can trust.

The update itself must be one that composes: applying tag A and then tag B on the same node must be equivalent to applying some single combined tag. Addition composes by adding the two tags together; a well-defined multiplication or affine transform composes the same way, as long as the composition rule matches how the operation actually combines.

A worked example

Take an array of 8 elements, all zero. A range update adds 5 to every element from index 2 to index 5, inclusive. Instead of visiting the four affected leaves directly, lazy propagation finds the single internal node whose range is exactly [2, 5], adds the tag "+5" to it, and updates that node's own summary immediately, since a node's own summary can always be corrected using the tag and the size of its range, without needing to touch its children.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    idx = 07    n = int(data[idx])8    idx += 19    ul, ur, uval = int(data[idx]), int(data[idx + 1]), int(data[idx + 2])10    idx += 311    ql, qr = int(data[idx]), int(data[idx + 1])12
13    tree_val = [0] * (2 * n)14    tree_lazy = [0] * (2 * n)15
16    def push(node: int, start: int, end: int) -> None:17        if tree_lazy[node] != 0:18            tree_val[node] += tree_lazy[node] * (end - start)19            if start + 1 < end:20                tree_lazy[2 * node] += tree_lazy[node]21                tree_lazy[2 * node + 1] += tree_lazy[node]22            tree_lazy[node] = 023
24    def range_update(node: int, start: int, end: int, l: int, r: int, val: int) -> None:25        push(node, start, end)26        if r <= start or end <= l:27            return28        if l <= start and end <= r:29            tree_lazy[node] += val30            push(node, start, end)31            return32        mid = (start + end) // 233        range_update(2 * node, start, mid, l, r, val)34        range_update(2 * node + 1, mid, end, l, r, val)35        push(2 * node, start, mid)36        push(2 * node + 1, mid, end)37        tree_val[node] = tree_val[2 * node] + tree_val[2 * node + 1]38
39    def range_query(node: int, start: int, end: int, l: int, r: int) -> int:40        push(node, start, end)41        if r <= start or end <= l:42            return 043        if l <= start and end <= r:44            return tree_val[node]45        mid = (start + end) // 246        return range_query(2 * node, start, mid, l, r) + range_query(2 * node + 1, mid, end, l, r)47
48    # The input gives inclusive index ranges; the tree's own convention is49    # half-open, so add 1 to each right endpoint before calling in.50    range_update(1, 0, n, ul, ur + 1, uval)51    print(range_query(1, 0, n, ql, qr + 1))52
53
54if __name__ == "__main__":55    main()

8
2 5 5
3 4

10

Querying the sum from index 3 to index 4 walks down from the root. When the walk reaches the node that still carries the "+5" tag, it pushes that tag down to its two children before continuing, so each child's own summary is now correct, and the tag on the parent is cleared. The query then proceeds using values that are actually up to date, and reports 10, since both index 3 and index 4 carry the added 5.

A second update that only partially overlaps the first, such as adding 3 to indices 1 through 3, forces the tree to split at the boundary between the previously updated range and the new one. Part of the previous tag has already been pushed down to smaller nodes by the time the second update reaches them, and any node that ends up needing both tags accumulates them by addition, exactly as a single node would if it had received both updates directly.

Common mistakes

Overwriting a node's existing pending tag instead of composing it with a new one is the most common error. A node that already owes "+5" and receives a new "+3" update owes "+8" in total, not just "+3"; always add the new tag to whatever tag is already pending, rather than replacing it.

Answering a query without pushing a node's tag down first is another. A query that reads a node's summary while children still owe an unpushed update returns a stale value that ignores the pending change.

A third mistake is treating a node's correction as if every element changed by the raw tag value. If a node's range holds 8 elements and the tag adds 5 to each one, the node's own summary sum needs to increase by 5 * 8 = 40, not by 5. Different summaries scale differently: a sum needs the range size, but a maximum does not need scaling by size at all.

Why it works, and the cost

Correctness rests on the same composability the tag itself relies on: two updates applied to the same node, one after another, are equivalent to one combined update, so it never matters how long a tag has waited to be pushed down. Each update touches $O(\log n)$ nodes directly, and each push costs constant time; summed over every operation, this keeps both operations at $O(\log n)$ amortized.

The space cost doubles compared to a plain segment tree, since a separate array holds the pending tags alongside the node summaries. The time cost per operation stays logarithmic, with a larger constant factor from the extra push step.

Making it fast on PyPy

Keep the tag itself as simple as the problem allows: a single number for a pure addition, a small tuple for an affine transform. Avoid wrapping tags in objects or dispatching through function pointers, since PyPy's JIT optimizes a small, repeated arithmetic operation far better than one hidden behind an abstraction. Precompute each node's range size once, rather than recomputing it inside the recursion on every call.