Difference Arrays
A difference array stores the change between neighbouring elements rather than the values themselves. Adding a constant to a whole range then becomes two writes instead of a loop, and one prefix-sum pass at the end turns the marks back into the finished array.
Many Overlapping Range Updates
The problem is stated the same way every time it appears: given an array and a list of q operations, each adding some value v to every element between indices l and r, produce the final array.
The direct approach loops from l to r for each operation. One update touching the whole array costs O(n), so q updates cost O(n·q). With 100,000 elements and 100,000 operations that is ten billion writes — far too slow.
The wasted effort is visible if you watch the writes. Overlapping ranges rewrite the same positions repeatedly, and each write immediately supersedes the last. Only the final value at each position matters, so the intermediate writes accomplish nothing.
The difference array removes them entirely by changing what is stored. Instead of the values, it records how each element differs from the one before it — so a range update no longer touches the range at all. It touches only the two positions where the pattern of change begins and ends.
That turns each update into O(1), and a single O(n) pass at the end reconstructs the answer. Total cost becomes O(n + q) rather than O(n·q).
The one condition is that all updates must be known before any query. The difference array is an offline technique: it batches the operations and materialises the result once. If updates and queries interleave, a Fenwick or segment tree is the right structure instead.
- Naive range updates cost O(n) each, O(n·q) overall
- Overlapping ranges rewrite the same cells repeatedly for nothing
- Recording changes makes each update touch only two positions
- Offline only — all updates first, then one reconstruction pass
Storing Changes Instead of Values
Define the difference array D from the original array A as D[0] = A[0] and D[i] = A[i] − A[i−1] for every later index. Each entry records the step from the previous element rather than the element itself.
For A = [3, 3, 5, 5, 5, 2], the difference array is D = [3, 0, 2, 0, 0, −3]. Note what the zeros mean: no change here. Long runs of equal values collapse to zeros, and only the boundaries carry information — which is exactly why range updates become cheap.
The reconstruction is the inverse operation: A[i] = D[0] + D[1] + … + D[i], a running total. Recovering the original is a single left-to-right pass accumulating the sum, done in place with D[i] += D[i-1].
So a difference array and a prefix sum are inverses of one another. A prefix sum turns values into cumulative totals so that range queries become O(1); a difference array turns values into steps so that range updates become O(1). Recognising them as a matched pair is the cleanest way to remember which applies to which problem.
If the array starts empty — all zeros, which is the common case in these problems — then D starts as all zeros too, and the two initialisations coincide. Most problems of this kind begin from zero, so the setup is usually just allocating n + 1 zeros.
That extra slot matters. Allocate the difference array with length n + 1, not n, so an update ending at the final index has a valid position to write its cancelling entry. Without it, the r + 1 write is out of bounds and requires a conditional — the extra slot removes the special case entirely.
D[0] = A[0], andD[i] = A[i] − A[i−1]thereafter- Zeros in D mean the value did not change there
- A prefix sum over D rebuilds A — they are exact inverses
- Allocate n + 1 entries so an update ending at n−1 needs no special case
The Two-Write Update
To add v to every element from index l to index r inclusive, perform exactly two writes: D[l] += v and D[r + 1] -= v.
The reasoning is worth stating rather than memorising, because it makes the technique obvious rather than magical. Adding v at position l means the running total is v higher from l onward — and since a prefix sum carries that increase forward indefinitely, every element from l to the end of the array rises by v. Subtracting v at r+1 cancels the increase from that point on, so the effect stops exactly where it should.
So the pair of writes describes an interval by marking where the change starts and where it stops, leaving everything between untouched. The interior positions inherit the change from the running total during reconstruction.
Multiple updates compose automatically by simple addition. Applying three overlapping ranges writes six entries in total, and the accumulated sums at each position produce the correct combined result. No ordering is required, and the updates commute — which is why the technique handles arbitrary overlap without any case analysis.
The complete algorithm is therefore three steps: allocate n + 1 zeros; apply every update as two writes at O(1) each; then run one prefix-sum pass at O(n). Total O(n + q).
Two implementation errors are common enough to name. Writing D[r] -= v instead of D[r + 1] -= v makes the update exclusive of its last element, producing an answer off by one range boundary. And forgetting the reconstruction pass entirely leaves the difference array itself being returned, which looks like plausible data and is wrong everywhere.
| Naive loop | Difference array | Fenwick / segment tree | |
|---|---|---|---|
| Range update | O(n) | O(1) | O(log n) |
| Read a value | O(1) | After the O(n) pass | O(log n) |
| Total for q updates | O(n·q) | O(n + q) | O(q log n) |
| Interleaved queries? | Yes | No — offline only | Yes |
D[l] += vandD[r+1] -= v— start the change, then cancel it- The prefix sum carries the change across the interior automatically
- Overlapping updates compose by addition, in any order
D[r]instead ofD[r+1]is the standard off-by-one bug
Terms, operations, and practical uses
Core operations
- Range AdditionAdding a specific value V to every element between an arbitrary start index L and end index R.
- Point UpdateModifying only specific boundary indices (L and R+1) to represent a bulk change, requiring strictly O(1) time.
- ReconstructionRunning a prefix sum pass over a difference array to calculate the final values of all elements.
State and timing
- Offline QueriesProcessing all modifications first, and only asking for the final answers after all updates are complete.
- Online QueriesInterleaving updates and queries (e.g., Update, Query, Update). Difference arrays fail here because reconstruction takes O(N).
- Sweep LineA broader algorithmic paradigm closely related to difference arrays, where events are processed in sorted order from left to right.
Use cases
- Interval OverlapCounting how many intervals overlap at any given point by adding 1 at the start and subtracting 1 after the end.
- Flight BookingsA classic problem: applying capacity changes across a range of flight segments efficiently.
- 2D Difference ArrayAdding a value to a 2D subgrid by placing four marks (start, end-right, end-down, end-diagonal) and running a 2D prefix sum.
Applying Range Updates via Difference Array
N = 5
D = [0] * (N + 1)
# Add 10 to [1, 3]
D[1] += 10
D[3+1] -= 10
# Subtract 5 from [2, 4]
D[2] -= 5
if 4+1 <= N:
D[4+1] += 5
# Reconstruct
A = [0] * N
current = 0
for i in range(N):
current += D[i]
A[i] = current
print('Final array:', A)#include <iostream>
#include <vector>
using namespace std;
int main() {
int N = 5;
vector<int> D(N + 1, 0);
// Add 10 to [1, 3]
D[1] += 10;
D[3+1] -= 10;
// Subtract 5 from [2, 4]
D[2] -= 5;
if (4+1 <= N) D[4+1] += 5;
// Reconstruct
vector<int> A(N, 0);
int current = 0;
for (int i = 0; i < N; i++) {
current += D[i];
A[i] = current;
}
cout << "Final array: [";
for (int i = 0; i < N; i++) {
if (i) cout << ", ";
cout << A[i];
}
cout << "]\n";
}class Main {
public static void main(String[] args) {
int N = 5;
int[] D = new int[N + 1];
// Add 10 to [1, 3]
D[1] += 10;
D[4] -= 10;
// Subtract 5 from [2, 4]
D[2] -= 5;
if (5 <= N) D[5] += 5;
// Reconstruct
int[] A = new int[N];
int current = 0;
for (int i = 0; i < N; i++) {
current += D[i];
A[i] = current;
}
System.out.println("Final array: " + java.util.Arrays.toString(A));
}
}Step through it
Running on Array of 5 zeros. Add 10 to [1,3], subtract 5 from [2,4]
Read all 11 Steps
- Start D has N+1 = 6 slots. The extra slot absorbs an "end" mark at index N, so no update ever writes out of bounds.
- Add 10 to [1,3] — open D[1] += 10 means "from index 1 onward, everything is 10 higher". One write, not three.
- Add 10 to [1,3] — close D[4] -= 10 cancels the increase just past R. The +10 now applies to exactly indices 1, 2 and 3.
- Subtract 5 from [2,4] — open D[2] -= 5. The two ranges overlap at indices 2 and 3, and the marks simply stack.
- Subtract 5 from [2,4] — close R = 4 is the last index, so the closing mark lands on the spare slot D[5] and is never read back.
- Two updates done in O(1) Four writes total covered two overlapping ranges. A naive loop would have touched 3 + 3 = 6 cells, and far more on real input sizes.
- Sweep i=0 Now one prefix pass turns the marks into values. running = 0 + D[0] = 0, so A[0] = 0 — outside both ranges.
- Sweep i=1 running = 0 + 10 = 10. The "open" mark switches the +10 on, and it stays on until something cancels it.
- Sweep i=2 running = 10 − 5 = 5. Index 2 sits in both ranges, so it carries both effects at once.
- Sweep i=3 D[3] is 0, so running stays at 5. Untouched slots cost nothing — the value simply carries forward.
- Sweep i=4 running = 5 − 10 = −5. The +10 range closed here, leaving only the −5. Total work: O(Q) marks plus one O(N) pass.
Where It Shows Up
Interval booking and scheduling. Counting how many meetings occupy each time slot, or how many flights carry passengers on each leg, is exactly this pattern: each booking is a range, and the answer is the accumulated occupancy. The 'corporate flight bookings' problem is the canonical statement of it.
Maximum overlap. Given a set of intervals, find the point covered by the most of them. Mark +1 at each start and −1 at each end, take the running sum, and the maximum of that running total is the answer. This is the sweep line technique, and a difference array is what it reduces to when the coordinates are small integers.
When the coordinates are large or sparse — timestamps, for instance — allocating an array indexed by coordinate is impractical. The same idea then uses a sorted list of events rather than an array: collect the +1 and −1 markers, sort by position, and sweep. Same reasoning, different container.
Two dimensions. The technique extends to grids for adding a value to every cell of a rectangle. Four writes are needed rather than two — +v at the top-left, −v at the two cells just past the right and bottom edges, and +v at the corner past both, correcting the region subtracted twice. Reconstruction is a 2-D prefix sum, first across rows and then down columns. The four-term pattern is inclusion–exclusion, the same correction that appears in 2-D prefix sums.
The technique is known in competitive programming as the imos method, from the Japanese community where it was popularised, and that name appears in problem editorials.
Choosing between the tools comes down to one question: are all updates known in advance? If yes, use a difference array — it is simpler, faster, and needs no tree. If updates and queries interleave, use a Fenwick tree for sums or a segment tree with lazy propagation for anything more general. A difference array is the offline special case, and preferring it when it applies is worth doing.
- Booking counts, occupancy, and maximum interval overlap
- Sparse coordinates use sorted events instead of an indexed array
- 2-D rectangle updates need four writes and inclusion–exclusion
- Offline updates → difference array; interleaved → Fenwick or segment tree