Difference array
mediumThe exact inverse of a prefix sum. Two writes apply an increment to any range, however wide, and a single pass turns the differences back into values.
O(1) per updateWorst O(n + q)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How difference array works
Adding v to every element of a[l..r] directly costs r - l + 1 writes, so q range updates cost O(n·q) at worst. The difference array records the same intent in two writes: diff[l] += v and diff[r+1] -= v. No element in between is touched - the update is a promise, redeemed later.
It works because diff is read back through a prefix-sum pass: running += diff[i] produces each final value. Adding v at l raises every running total from l onward; subtracting v at r+1 cancels the raise from r+1 onward. Net effect: exactly [l..r] is incremented, whatever its width. Two writes for a range of ten or of ten thousand.
This is the prefix sum run in reverse. Prefix sums pay O(n) once so range reads become O(1); difference arrays make range writes O(1) and pay O(n) once at the end to materialise. The constraint: all updates must land before the reads. Interleaved reads and writes need a Fenwick or segment tree instead.
Step by step
- Start with six zeros and seven diff slots, all zero. Two updates are queued: add 3 to [1..4], add 2 to [0..2].
- First update: diff[1] += 3 and diff[5] -= 3. diff reads 0, 3, 0, 0, 0, -3, 0 - two writes for a four-wide range.
- Second update: diff[0] += 2 and diff[3] -= 2. diff becomes 2, 3, 0, -2, 0, -3, 0. Both updates recorded in four writes.
- Materialise with a running sum: 2, then 2 + 3 = 5, then 5 + 0 = 5. The first three values are 2, 5, 5.
- Continue: 5 - 2 = 3, then 3 + 0 = 3, then 3 - 3 = 0. Final array: 2, 5, 5, 3, 3, 0.
- Check by hand: [1..4] got the 3, [0..2] got the 2, index 5 got nothing. Every update cost two writes, however wide its range.
Complexity
| Best case time | O(1) per update |
|---|---|
| Worst case time | O(n + q) |
| Space | O(n) |
Reference implementation
Python
def range_updates(n, updates):
"""Apply many range increments in O(1) each, then materialise once."""
diff = [0] * (n + 1)
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v # cancels the effect after r
out, running = [], 0
for i in range(n):
running += diff[i] # prefix sum of the differences
out.append(running)
return outJavaScript
function rangeUpdates(n, updates) {
const diff = new Array(n + 1).fill(0);
for (const [l, r, v] of updates) {
diff[l] += v;
diff[r + 1] -= v; // cancels after r
}
const out = [];
let running = 0;
for (let i = 0; i < n; i++) { running += diff[i]; out.push(running); }
return out;
}Worth noticing
The exact inverse of a prefix sum
Prefix sums make range *queries* O(1) after an O(n) build. Difference arrays make range *updates* O(1) before an O(n) finalise. Same machinery, run in the other direction.
Why `diff[r+1] -= v`
Adding v at l makes every later prefix sum v larger. Subtracting v at r+1 cancels that from r+1 onwards, so the increment lands on exactly [l, r] - two writes, whatever the range width.
The right tool when updates come in bulk
q range updates on n elements cost O(n + q) instead of O(n·q). If updates and queries interleave you need a Fenwick or segment tree instead - but for offline batches this is far simpler and faster.
Common pitfalls
- Sizing diff at n instead of n + 1. An update ending at the last index writes diff[n], and the short array crashes or silently drops the cancellation.
- Forgetting the cancelling write at r + 1, which turns add v to [l..r] into add v to everything from l to the end.
- Reading values before the finalise pass. diff stores deltas, not values - until the running sum runs, the array is an IOU, not an answer.
- Placing the cancellation at r instead of r + 1, which shorts the range by one: a[r] was supposed to be included.
- Using it when queries interleave with updates - the two-write trick only pays because the O(n) materialise happens once, after everything.
Where it is used
- Bulk range increments applied offline: score adjustments, salary bands, brightness over image rows.
- Interval overlap counting: +1 at each start, -1 past each end, and the materialise pass yields how many intervals cover each point.
- Corporate flight bookings and its family - problems that end with output the final array after these q range operations.
- The imos method extends the same two-write cancellation to 2-D grids for rectangle updates.
Frequently asked questions
What are the time and space complexity of a difference array?
Each range update is O(1) - two writes, no matter how wide the range. The single materialising pass is O(n), so q updates on n elements total O(n + q), against O(n·q) for applying every range directly. Space is O(n) for the n + 1 diff slots.
What is the difference between a prefix sum and a difference array?
They are inverses. A prefix sum precomputes so range reads become O(1); a difference array defers so range writes become O(1). Running a prefix-sum pass over the differences reconstructs the values - which is literally how the finalise step works here.
Why subtract at r + 1 and not at r?
The running sum picks up diff[r] while computing a[r], so a[r] still receives the increment - the range is inclusive. The cancellation must land one slot later, at r + 1, so the first element it affects is a[r+1], the first one outside the range.
When do I need a Fenwick tree instead?
The moment reads and writes interleave. A difference array answers nothing until its one finalise pass, so it suits offline batches: all updates first, then all reads. A Fenwick tree does point updates and prefix queries in O(log n) each, in any order, at the cost of more code.