The setup
Imagine you must apply hundreds of range additions, each saying add a value to every element from left to right, and only at the end read the final array. Touching every element per update would be wasteful. A difference array turns each range update into two quick marks.
How it works
The difference array stores, at each index, the change from the previous element. To add a value across a range:
- Add the value at the left index.
- Subtract the value just past the right index.
These two marks describe a step up that begins at left and a step down that ends after right. Each update is constant work regardless of range length.
Reconstructing
After all updates, take a single prefix sum of the difference array. Each element accumulates the net effect of every step up and step down before it, recovering the final values for the whole array in one linear pass.
Where it shines
The difference array is perfect for offline batch updates where queries come only after all changes. Booking heat maps, range increment puzzles, and flight booking style problems all fit. It is the static cousin of the Fenwick range update trick.
Key idea
A difference array records each range addition as two endpoint marks, and one prefix sum at the end reconstructs every final value.