Lazy Propagation Structure

Add a lazy array alongside the tree array:

class LazySegmentTree:
    function init(n):
        this.n = n
        this.tree = array of 4*n zeros
        this.lazy = array of 4*n zeros

lazy[node] stores pending updates that haven't been propagated to children yet.

For "add $v$ to range": lazy[node] means "add $v$ to all elements in this node's range."

Before accessing a node's children, always push down any lazy value first. This guarantees correctness.