Lazy Propagation
Learn Lazy Propagation (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
O(log n) RANGE Updates, Not Just Point Updates Plain Segment Tree updates ONE element in O(log n). Updating an entire RANGE naively means updating each element individually - O(range size × log n), far too slow for large ranges. Lazy propagation fixes this: mark a node's update as PENDING instead of immediately pushing it to all descendants, only propagating it down when that subtree is actually visited later.