The inverse of a prefix sum
A difference array stores the change between consecutive elements rather than the values themselves. It is the natural partner of the prefix sum: running a prefix sum over the differences reconstructs the original array.
Cheap range updates
The payoff is range updates. To add a value across a range from index i to index j, you make just two edits to the difference array:
- Add the value at index i, where the range begins.
- Subtract the value just past index j, where the range ends.
Each range update is now constant work no matter how wide the range. After all updates are recorded, a single prefix sum pass materializes the final array.
When to reach for it
This technique fits problems with many overlapping range increments followed by a single read of the result, such as marking attendance over intervals or accumulating booking counts. Doing the updates directly would cost the range width each time; the difference array defers that cost to one final pass.
Key idea
A difference array turns each range increment into two boundary edits, then one final prefix sum pass reconstructs the array, making batches of overlapping range updates cheap.