Algorithms / Difference Arrays
Least You Need to Know: Difference Arrays, Boundary Marking, and Range Updates
Difference arrays invert the prefix-sum idea: instead of storing cumulative totals directly, they store **where changes begin and end**. After marking update boundaries, one prefix sweep reconstructs the final values.
The least you need to know
- A range increment can be marked by adding at the start and subtracting just after the end.
- Taking prefix sums of the difference array reconstructs final values.
- Difference arrays are efficient for many offline range updates.
- They are best when updates come first and pointwise reconstruction comes later.
- Boundary marking is simpler than touching every element of every updated range.
Key notation
diff[l] += x
start applying +x at position l
diff[r+1] -= x
stop applying +x after position r
prefix of diff
reconstructed final array
Tiny worked example
- To add `+3` on interval `[2, 4]`, mark `diff[2] += 3` and `diff[5] -= 3`.
- After all updates, take prefix sums of `diff`.
- The running total applies the update exactly on positions `2, 3, 4`.
- This converts repeated range updates into constant-time boundary edits plus one final sweep.
Common mistakes
- Students often forget the `r+1` stop marker or mishandle the boundary when `r` is the last index.
- Difference arrays are usually offline; they do not instantly answer arbitrary interleaved queries.
- You reconstruct actual values only after prefixing the differences.
How to recognize this kind of problem
- There are many interval increments followed by final array inspection.
- You care about batch processing rather than online query/update interleaving.
- Boundary markers are easier than touching every interior position.