Suppose you need to add a value to every element of a wide range — add +2 to indices 1..3 — and you have to do this many times before you ever look at the array again. Touching every element in every range is slow. A difference array records each range update as just two edits, then rebuilds the whole array once at the end with a single prefix sum.
Keep a helper array diff where diff[i] stores the change between element i - 1 and element i.
To add v to every element in l..r, do diff[l] += v and diff[r + 1] -= v — both O(1).
A running prefix sum of diff then recovers the final array in one O(n) pass.
It is the exact mirror of prefix sum: prefix sum answers range queries fast, while a difference array applies range updates fast. For add +2 to [1,3] then add +3 to [2,5] over six slots, the final array is [0, 2, 5, 5, 3, 3].
Intuition
Think of a paint roller. Adding v across a range is like pressing the roller down at index l and lifting it at index r + 1. You only mark two events: "start adding v here" and "stop adding v here." The +v at l switches the effect on; the -v at r + 1 cancels it so it does not bleed past the range.
While you are recording updates, the array stays in this cryptic "changes" form. The magic is the rebuild: walking left to right with a running total, the +v turns the effect on and it stays on (the running sum carries it forward) until the matching -v turns it back off. The running total at each position is exactly the sum of all updates that cover it.
Walk through it
The animation on the right shows two rows. The top row is diff, which is one cell longer than the data (7 cells for 6 elements) and starts all zeros. The bottom row is out, the array we will recover.
First we apply add +2 to [1,3]. The pointer l lands on diff[1], which becomes +2, and r+1 lands on diff[4], which becomes -2. Then add +3 to [2,5]: diff[2] becomes +3 and diff[6] becomes -3. After both updates diff is [0, 2, 3, 0, -2, 0, -3] — only four cells touched for two whole-range updates.
Now the sweep. A pointer i walks diff left to right while run accumulates: run += diff[i], and that running value is written into out[i]. Watch run climb to 2 at index 1, to 5 at index 2 (where both updates overlap), hold at 5 through index 3, drop to 3 at index 4 when the first update's -2 kicks in, and stay 3 to the end. The recovered array is [0, 2, 5, 5, 3, 3], and each cell locks in as sorted.
The code, line by line
def apply_updates(n, updates):
diff = [0] * (n + 1)
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v
out, run = [], 0
for i in range(n):
run += diff[i]
out.append(run)
return outdiffhas lengthn + 1, notn— the extra trailing slot is wherediff[r + 1] -= vwrites when a range ends at the last index, so it never goes out of bounds.- Lines 4–5 are the whole update:
diff[l] += vswitches the+veffect on atl, anddiff[r + 1] -= vswitches it off just pastr. Each range update is O(1) no matter how wide. - Line 8 is the rebuild:
runis a prefix sum ofdiff, so it equals the total of every update whose range covers indexi. - Line 9 records that running value as the final element
out[i]. - The whole recovery is one pass, so applying
qupdates and rebuilding costsO(q + n)instead ofO(q * n).
Complexity
| Case | Time | Notes |
|---|---|---|
| Each range update | O(1) (fast) | two array writes, regardless of range width |
| Rebuild the final array | O(n) (moderate) | one prefix-sum sweep over diff |
| q updates then rebuild | O(q + n) (moderate) | vs O(q * n) updating each element directly |
O(n) (moderate)The payoff grows with the number of updates. Adding v to a range of width w the naive way costs O(w) per update; a difference array makes it O(1) and defers all the real work to a single O(n) rebuild. The cost is O(n) extra space for the diff array.
When to use / pitfalls
Reach for a difference array when you face many range updates and only need the final array once at the end — flight-booking seat counts, painting intervals, range increment problems, or the Car Pooling question. The same trick lifts to 2D (a difference matrix for adding to rectangles). If updates and reads are interleaved instead of batched, a difference array goes stale — that is when a Fenwick tree or segment tree with lazy propagation takes over.
Two classic traps. First, size diff as n + 1, not n — otherwise diff[r + 1] overflows when a range
ends at the last index. Second, mind inclusivity: for an inclusive range l..r the closing edit is at
r + 1, because the +v must remain active through index r and only cancel afterward. Writing diff[r]
instead of diff[r + 1] drops the last element of every range.
Practice
diff is all zeros over 6 slots. After add +2 to [1,3] and add +3 to [2,5], what does diff look like (7 cells)?
1. To add v to every element of the inclusive range l..r, which two edits do you make?
2. Why must diff have length n + 1 instead of n?
3. How do you recover the final array from diff?
4. For 6 slots, after add +2 to [1,3] then add +3 to [2,5], what is the final array?