Segment Tree: Lazy Propagation

A plain segment tree answers a range query (like "sum of indices 1 to 3") in O(log n), but a range update — "add 5 to every element in [1, 2]" — is slow if you walk down to each leaf. Lazy propagation fixes that: when a node's whole segment is covered by the update, you stop there, stamp a small lazy tag recording the pending change, and adjust that node's stored answer in O(1). You only push the tag down to children later, when a query actually needs to look inside that node. Both range update and range query stay O(log n).

The tree we animate has 7 nodes over [1, 2, 3, 4]: a root covering [0,3] (sum 10), two internal nodes for [0,1] (sum 3) and [2,3] (sum 7), and four leaves holding the values.

Intuition

Think of a lazy tag as an IOU pinned to a node. When an update fully covers a node's segment, fixing every leaf underneath would be wasteful — they all change by the same amount, and nobody is asking for them yet. So we update the node's own summary value (its sum), pin an IOU for the amount per element, and walk away. The subtree below is momentarily stale, but the node knows exactly how to repay the debt the instant someone peers inside it.

That "peering inside" is the only thing that forces work. A query that lands on a fully-covered node reads its (already-correct) sum and never descends. A query that must split between children first calls push_down: it pays the IOU to each child — bumping each child's sum and re-pinning a smaller IOU on it — then clears its own tag. Because every update and every query touch only O(log n) nodes, and each node does O(1) tagging, the whole thing stays logarithmic.

Walk through it

Step through the animation on the right. Each circle shows its subtree sum; a fully-covered node also shows a lazy +k tag.

First we run update, adding +5 to range [1, 2]. We start at the root [0,3]: the update only partially overlaps, so we recurse. At nL [0,1] it is still only a partial overlap, so we recurse again — and node [1] is fully inside [1,2]. Instead of touching a leaf we stamp lazy +5 on it and bump its sum from 2 to 7. Coming back up, nL repairs its own sum from its children: 1 + 7 = 8. We then recurse right into nR [2,3], where node [2] is fully covered — lazy +5, sum 3 → 8 — and repair the sums up the spine: nR becomes 12 and the root becomes 20. Two elements changed, the ancestors all reflect it, yet no leaf was ever rewritten.

Then we run query for sum([0, 1]). The root partially overlaps, so we go down (pushing any pending root tag — it has none). nL [0,1] exactly matches the query, so it returns its stored sum 8. The animation also illustrates push_down: had the query needed nL's children, it would flush nL's tag into them first; here the +5 already lives on the leaf, so pushing is a no-op. The answer is 8 = 1 + (2 + 5) — correct, with the update never having been forced all the way down.

The code, line by line

def update(node, lo, hi, l, r, val):
    if r < lo or hi < l:        # no overlap
        return
    if l <= lo and hi <= r:     # full cover: stop, tag lazy
        tree[node] += val * (hi - lo + 1)
        lazy[node] += val
        return
    push_down(node, lo, hi)     # partial: clear before recursing
    mid = (lo + hi) // 2
    update(2*node,   lo,    mid, l, r, val)
    update(2*node+1, mid+1, hi, l, r, val)
    tree[node] = tree[2*node] + tree[2*node+1]
 
def query(node, lo, hi, l, r):
    if r < lo or hi < l:        # no overlap
        return 0
    if l <= lo and hi <= r:     # full cover
        return tree[node]
    push_down(node, lo, hi)     # flush lazy to children
    mid = (lo + hi) // 2
    return (query(2*node,   lo,    mid, l, r) +
            query(2*node+1, mid+1, hi, l, r))

• Lines 2-3 / 15-16 are the no-overlap base case: if the node's segment [lo, hi] is entirely outside the query/update range [l, r], there is nothing to do.
• Lines 4-7 are the heart of lazy propagation: when [lo, hi] is fully inside [l, r], we add val to every element by adjusting the stored sum once (val * length) and pinning lazy[node] += val. We return immediately — no recursion to the leaves.
• Line 8 (and 19) call push_down: before recursing into a partially-covered node, flush its pending tag into both children so they are correct before we read or modify them. push_down does tree[child] += lazy[node] * child_len; lazy[child] += lazy[node] for each child, then resets lazy[node] = 0.
• Line 12 is the merge step: after updating children, a parent recomputes its sum as the sum of its two children, so every ancestor stays consistent.
• Lines 17-18 are the query full-cover case: a node whose segment lies entirely in the query range returns its stored sum directly — already correct, since any tag affecting it was applied to that sum when it was set.

Complexity

Without lazy tags, a single range update could touch O(n) leaves. The tag lets a fully-covered subtree absorb the update in O(1), so an update visits the same O(log n) nodes a point query would. push_down adds only O(1) work per node on the query path, leaving the overall bound at O(log n). The tree itself needs O(n) space for the tree array plus an equal-sized lazy array.

When to use / pitfalls

Practice