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)What to notice
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.
Saved in this browser - no sign-up, nothing sent anywhere.
How a 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;
}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.