Lazy Propagation for Range Updates
Defer updates over whole ranges.
Lazy Propagation for Range Updates is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Range Update Problem
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. 😰
The Lazy Idea
Lazy propagation lets a node remember a pending change without pushing it to children yet. Work is deferred until you actually need those children.
A Second Array for Pending Work
Alongside the tree we keep a lazy array. lazy[node] stores an update that applies to that node's whole range but is not yet pushed down.
lazy = [0] * (4 * n)Apply to a Whole Node
When an update covers a node fully, adjust its stored value and stack the change into lazy, then stop. No need to descend.
seg[node] += (r - l + 1) * val
lazy[node] += valPush Down Before Descending
Before visiting children, push down any pending lazy value into both of them. This keeps the children correct exactly when you read them.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Three Cases per Node
At each node the query range is disjoint, fully covering, or partial. Skip, apply lazily, or recurse into both halves respectively.
Lazy Updates Stay Logarithmic
A range update touches only O(log n) nodes because full-cover nodes stop early. That is the whole payoff of going lazy. ⚡
Queries Push Down Too
Range queries must also push down before recursing, so they read fresh child values. Forgetting this is the classic lazy bug.
Pull Up After Recursion
After updating children, recombine the parent from them. This pull-up keeps every internal node consistent with its subtree.
seg[node] = seg[2*node] + seg[2*node+1]Assignment vs Addition
Lazy works for many ops, but assignment and addition combine differently. Decide how two pending updates merge before you code it.
When Lazy Is Worth It
Reach for lazy propagation only when you truly need range updates. For point updates alone, a plain segment tree is simpler and enough.
Quick Check
What must happen before recursing into a node's children?
Recap: Deferred Updates
You learned lazy propagation: store pending changes, push down before descending, pull up after, and earn O(log n) range updates. 🎉
Frequently asked questions
Is the “Lazy Propagation for Range Updates” lesson free?
Yes — the full text of “Lazy Propagation for Range Updates” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Lazy Propagation for Range Updates”?
Defer updates over whole ranges. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Lazy Propagation for Range Updates” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Fenwick Tree for Prefix Sums
- Inversions with a BIT
- Segment Tree: Build & Query
- Lazy Propagation for Range Updates