The problem
Suppose you must add a value to every element in a range, and you must do this for many ranges. Doing each update directly touches every element in the range, which is slow when ranges are large and updates are many.
The difference trick
Instead of storing the array, store the differences between consecutive elements. Adding a constant to a whole range then becomes two small edits:
- Add the value at the start of the range.
- Subtract the value just after the end of the range.
Each range update is now two single point edits, no matter how wide the range is. After all updates are recorded, a single left to right prefix sum over the difference array reconstructs the final values.
Why it works
A prefix sum turns each start mark into a step up that carries forward, and each end mark into a step down that cancels it. The value stays raised exactly across the intended range.
This pattern generalizes to two dimensions, where four corner edits stamp a rectangle, and it underlies many sweep style techniques.
Key idea
Store differences so a range update costs two point edits, then run one prefix sum to recover the final array.