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.
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
Worked example
- To add
+3on interval[2, 4], markdiff[2] += 3anddiff[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+1stop marker or mishandle the boundary whenris 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Memoization vs Tabulation.
Least You Need to Know: Memoization vs TabulationRelated lessons
Keep going with nearby lessons in the same topic.