Skip to content

Lazy Propagation on Segment Trees

Lazy propagation defers range updates: each node stores a pending update applied to its whole segment; when you descend for a query or narrower update, you push the lazy value to children and clear the parent’s tag.

Typical operations: range add or range assign with range sum / min queries.

Idea

  • Node holds aggregate (sum, min, …) for its segment.
  • Lazy tag means “this entire segment still owes +v” (or “set to v”).
  • On query(l,r) or update that splits a node: call push(node) to apply lazy to children before recursing.

Pattern (sketch)

// tree[1..4n] aggregates, lazy[1..4n] pending adds — illustration only
void pushAdd(int node, int len) {
    if (lazy[node] == 0) return;
    int add = lazy[node];
    tree[2 * node] += add * (len / 2);
    tree[2 * node + 1] += add * (len / 2);
    lazy[2 * node] += add;
    lazy[2 * node + 1] += add;
    lazy[node] = 0;
}

Combine order matters: assignment and addition need consistent ordering (often two tags with defined precedence).

Complexity

Range update and query remain \(O(\log n)\) per operation with correct push/apply.