TRT
Sign in

Expert · Module 26 · Lesson 3 of 4

Lazy propagation

A range update that covers a whole subtree records its work in one lazy slot instead of rewriting every leaf. Queries collect that work on the way down, which keeps both updates and queries at O(log n).

Pro — members onlyAbout 13 minutes

By the end you can

  • Explain what a lazy slot records and the moment a pending operation has to be pushed down
  • Trace a range add and a query across the boundary, then verify every node sum
  • Identify the two classic bugs: not pushing before descending, and not clearing after pushing

Builds on Segment trees.

01 · A question first

Adding 100 to every element of a ten-million-element array with a plain segment tree means ten million leaf writes. Lazy propagation makes the same update touch a few dozen nodes and postpones the rest. The catch is that every later query must collect that postponed work first, and when it forgets, the answer is wrong without any error being raised.

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Why touching every leaf is too expensive
  • One slot per node
  • Push only where a child will be read
  • Why the values must compose
  • Verifying every node sum
  • Where it is used
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · hard · LeetCodeRange moduleTrack a set of half-open ranges under additions, removals and coverage queries, keeping disjoint intervals sorted.Practice · medium · LeetCodeDesign a stack with increment operationSupport push, pop and adding a value to the bottom k elements, all in O(1), by recording increments lazily and passing them down on pop.

Asked in interviews

Something wrong with this lesson? Report a problem