Lazy Segment Tree
Learn Lazy Segment Tree (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Lazy Propagation: Range Updates and Range Queries A plain segment tree updates one element at a time. To add v to every element of a range and still answer range sums, use lazy propagation : when an update covers a whole block, change that block's sum and leave a "pending add" note (the lazy value) on it instead of descending to the leaves. The note is pushed down to the children only when a later operation needs to look inside that block. Both operations stay O(log n) .