Lazy Propagation for Range Updates

What if a query says add 5 to every element from l to r? Touching each leaf is O(n) per update, far too slow for many range updates. 😰

Lazy propagation lets a node remember a pending change without pushing it to children yet. Work is deferred until you actually need those children.