Lazy propagation: range update, range query

A plain segment tree does point update plus range query. But contests love range updates: "add 5 to every element in [l, r]." Done naively — descend to all the leaves and bump each — a single range update is O(n log n), worse than a flat loop. Lazy propagation rescues it by being deliberately lazy about the work.

The idea: when an update fully covers a node's segment, do not recurse into its children. Instead, update that node's aggregate immediately and leave a sticky note on it — a lazy tag recording "everyone below me still owes +5." The children stay stale. You only push down the tag — apply it to the children and clear it — at the moment you actually need to descend through that node for a later operation.

void push_down(int node, int lo, int hi) {
    if (lazy[node] == 0) return;
    int mid = (lo + hi) / 2;
    apply(2*node,   lo,    mid, lazy[node]);  // child += tag * size
    apply(2*node+1, mid+1, hi,  lazy[node]);
    lazy[node] = 0;                            // tag discharged
}

Concretely, add 3 to [0, 3] of a size-8 tree. The root [0, 7] is not fully covered, so push down (nothing pending yet) and recurse. The left child [0, 3] is fully covered: bump its aggregate by 3 × 4 = 12, set its lazy tag to 3, and stop — its four leaves are never touched. The work is O(log n), and the leaves under [0, 3] only learn about the +3 if some future query forces a descent through that node.

The invariant that keeps this honest: a node's stored aggregate always already includes its own lazy tag; the tag is the debt owed only to its children. Hold that invariant and range update, range query, and point query all become O(log n).

Lazy propagation is the ceiling of this unit — with it, the segment tree handles range-add-range-sum, range-assign-range-max, and a dozen other combinations, each a different apply and push_down. Get the invariant right and the rest is bookkeeping.