Lazy Propagation
Add to or assign a whole range in O(log n) by leaving a pending note on a segment tree node and pushing it down only when needed.
The problem
You have an array of n numbers. Each query is either "add v to every element of a[l..r]" or "print the sum of a[l..r]". The plain segment tree handles one changed element in O(log n). Here one query changes up to n elements.
1 of 9