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.