Lazy Propagation
The template handles point updates (set arr[i] = v). But many problems need range updates: “add 5 to every element in [i, j]” or “set all of [i, j] to x.” Doing that naively — updating each leaf — is O(range × log n), which collapses to O(n log n) for a big range. Lazy propagation gets it back to O(log n).
The key insight: don’t push work you don’t need yet
When you add 5 to a whole range [i, j], the recursion already finds the same O(log n) canonical nodes that fully cover [i, j] (the query decomposition). The trick: update those covering nodes’ aggregates immediately, but don’t recurse into their children. Instead, leave a note — a lazy tag — saying “everyone below me still owes a +5.” Only when a later operation actually needs to go below that node do you “push down” the pending update to its children.
Lazy propagation = “I’ll deal with it when someone asks.” A node accepts a range update by adjusting its own aggregate and storing a lazy tag for its subtree. The subtree stays untouched — possibly forever, if no query ever drills into it. The deferred work is only ever done along paths that are actually visited, which keeps every operation O(log n).
The two new pieces
You add one array and one helper:
lazy[]— a parallel array;lazy[node]holds a pending update fornode’s entire subtree that hasn’t been pushed to its children yet.pushDown(node)— before recursing into a node’s children, apply this node’s lazy tag to both children (update their aggregates and their lazy tags), then clear it.
Applying an update to a node
For “add v to range” on a node covering a range of length len: the node’s sum increases by v × len, and its lazy tag accumulates +v (to forward to children later).
Pushing down
Before you descend past a node that has a pending tag, give the tag to both children (adjust each child’s aggregate by v × child_len and add v to each child’s lazy tag), then reset this node’s tag to 0.
Querying
Same three-case recursion as before — but pushDown first whenever you’re about to recurse into children, so the values you read are correct.
Range-add, range-sum with lazy propagation
Always pushDown before recursing into children — in both update and query. If you read or modify a child while the parent still holds an unresolved lazy tag, you’ll use stale child values and get wrong answers. The rule is mechanical: the moment you’re about to descend past a node, settle its debt to its children first. Forgetting pushDown in the query path (people often add it only to update) is the classic lazy-propagation bug.
Assignment vs increment
The example above is range-add (+= v), which accumulates. Range-assign (set all to x) is different: a later assign overwrites an earlier one rather than stacking, so the lazy tag needs a “has a pending assignment?” marker and pushDown replaces rather than adds. The structure is identical; only how two pending updates compose changes. Always ask: do my updates stack or overwrite?
Quick check
Next: Fenwick Tree (BIT) — a smaller, faster structure for the common prefix-sum case, with the i & -i bit trick demystified.