Data Structures19 sections · 729 units
Open in Course

The Range Update Problem

Why lazy propagation exists

What if you need to update a range, not a single element? "Add 5 to all elements from index 3 to 7." Naive approach: call point update for each index.

That's O(klogn)O(k \log n) for a range of size kk. Too slow for large ranges. Lazy propagation solves this.

Instead of immediately updating all affected nodes, you "lazily" mark nodes and propagate updates only when needed.

The idea: when updating a range, if a node's segment is completely inside the update range, mark it with a "lazy" value and stop. Don't recurse further.

When you later query or update through this node, propagate the lazy value to children first. This achieves O(logn)O(\log n) range updates.