Difference Arrays and 2D Prefix Sums
Many updates, then one read
Range Addition: start with 5 zeros and apply the updates [[1, 3, 2], [2, 4, 3], [0, 2, -2]], where [start, end, inc] adds inc to every position from start to end. The result is [-2, 0, 3, 5, 3].
The direct way adds to every cell of every range:
def get_modified_array_slow(length, updates):
result = [0] * length
for start, end, inc in updates:
for i in range(start, end + 1): # touches every index of every range
result[i] += inc
return result
It returns [-2, 0, 3, 5, 3], but each update costs the length of its range. With 100,000 positions and 10,000 updates that each cover everything, that's 1,000,000,000 additions, and nobody reads the array until the end.
Think about what an update really changes. Inside the range, neighbours still differ by what they differed by before; the only places the difference between neighbours changes are where the range starts (it jumps up by inc) and just after it ends (it drops back). So store differences, make two writes per update, and rebuild the array once with a running total, the tool from Introduction to Prefix Sums.
Two writes, one running total
A difference array d holds how much each position differs from the one before it, so the running total of d is the array itself. Adding inc to start..end raises the difference at start by inc and lowers it at end + 1 by inc; nothing in between changes. The running total picks inc up at start and carries it until it's cancelled just past end.
Give d one spare slot at the end, so end + 1 is a valid index even when the range reaches the last position:
Range Addition: 5 zeros, updates [[1, 3, 2], [2, 4, 3], [0, 2, -2]] — The top row is d, with its spare slot at the end; the bottom row is the array, filled by the running total of d.
vector<int> getModifiedArray(int length, const vector<vector<int>>& updates) {
vector<int> diff(length + 1, 0); // one spare slot, so end + 1 is always a valid index
for (const auto& u : updates) {
diff[u[0]] += u[2]; // the range starts here
diff[u[1] + 1] -= u[2]; // and stops just after its last index
}
vector<int> result(length);
int running = 0;
for (int i = 0; i < length; i++) {
running += diff[i]; // the running total of the differences
result[i] = running;
}
return result;
}
def get_modified_array(length, updates):
diff = [0] * (length + 1) # one spare slot, so end + 1 is always a valid index
for start, end, inc in updates:
diff[start] += inc # the range starts here
diff[end + 1] -= inc # and stops just after its last index
result, running = [], 0
for i in range(length):
running += diff[i] # the running total of the differences
result.append(running)
return result
static int[] getModifiedArray(int length, int[][] updates) {
int[] diff = new int[length + 1]; // one spare slot, so end + 1 is always a valid index
for (int[] u : updates) {
diff[u[0]] += u[2]; // the range starts here
diff[u[1] + 1] -= u[2]; // and stops just after its last index
}
int[] result = new int[length];
int running = 0;
for (int i = 0; i < length; i++) {
running += diff[i]; // the running total of the differences
result[i] = running;
}
return result;
}
function getModifiedArray(length, updates) {
const diff = new Array(length + 1).fill(0); // one spare slot, so end + 1 is always a valid index
for (const [start, end, inc] of updates) {
diff[start] += inc; // the range starts here
diff[end + 1] -= inc; // and stops just after its last index
}
const result = [];
let running = 0;
for (let i = 0; i < length; i++) {
running += diff[i]; // the running total of the differences
result.push(running);
}
return result;
}
Each prints -2 0 3 5 3, 0 0 3 3 5 2 2 and 1 1 1 for 5 zeros with [[1, 3, 2], [2, 4, 3], [0, 2, -2]], 7 zeros with [[2, 4, 3], [4, 6, 2]], and 3 zeros with [[0, 2, 1]]. q updates cost 2q writes, and the rebuild is one pass: O(n + q) time instead of O(n · q), and O(n) space.
Car Pooling: off at the stop, not after it
Car Pooling is the same idea with passengers: [passengers, from, to] get on at from and are off at to. So the −passengers goes at to itself, not at to + 1: a group getting off at 5 frees its seats for a group getting on at 5. Locations are at most 1000, so 1001 slots cover every stop.
def car_pooling(trips, capacity):
change = [0] * 1001 # stops 0..1000
for passengers, start, stop in trips:
change[start] += passengers # they get on at start
change[stop] -= passengers # and are off at stop, before anyone gets on there
in_car = 0
for c in change:
in_car += c
if in_car > capacity:
return False
return True
It prints False, True and True for [[2, 1, 5], [3, 3, 7]] with capacity 4, the same trips with capacity 5, and [[2, 1, 5], [3, 5, 7]] with capacity 3. In the last one 2 people leave at 5 and 3 get on at 5, so the car never holds more than 3.
Check each problem for which kind of end it has. Range Addition's end is the last index that changes (write at end + 1). Car Pooling's to is the first stop where the passengers are gone (write at to).
Prefix sums on a grid
Range Sum Query 2D - Immutable asks for the sum of any rectangle of a matrix, many times. Do in two directions what Introduction to Prefix Sums did in one: P[r][c] is the sum of everything above and left of position (r, c), that is rows 0..r − 1 and columns 0..c − 1, with a row and a column of zeros in front.
Building it. P[r + 1][c + 1] is the new cell, plus the block above it, plus the block to its left. Those two blocks overlap in the block above-left, which got counted twice, so take it off once:
P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] − P[r][c]
Building the table for [[1, 2, 3], [4, 5, 6], [7, 8, 9]] — Amber: the two blocks added. Violet: the overlap taken off. Blue: the new total.
Asking it. For rows r1..r2 and columns c1..c2, start from everything down to the bottom-right corner, take off the rows above the rectangle and the columns to its left, and add back the top-left block, which was taken off twice:
sum = P[r2 + 1][c2 + 1] − P[r1][c2 + 1] − P[r2 + 1][c1] + P[r1][c1]
![Left, a 5 by 5 grid with the rectangle rows 2 to 3, columns 1 to 3 shaded: the rectangle you want. It equals four totals, each drawn as a small grid with the rectangle outlined: P[r2+1][c2+1], everything down to its bottom-right corner, minus P[r1][c2+1], the rows above it, minus P[r2+1][c1], the columns left of it, plus P[r1][c1], the top-left block that was taken away twice.](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/dsa-content-52c0a882-3bdf-4e4c-87f3-6b50d28f2e17/four-totals.webp)
class NumMatrix {
vector<vector<long long>> P; // P[r][c] = sum of rows 0..r-1 and columns 0..c-1
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
P.assign(m + 1, vector<long long>(n + 1, 0));
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) // the block above and the block left both hold P[r][c]
P[r + 1][c + 1] = matrix[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
}
long long sumRegion(int r1, int c1, int r2, int c2) { // the corner was taken away twice
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
};
class NumMatrix:
def __init__(self, matrix):
m, n = len(matrix), len(matrix[0])
self.P = [[0] * (n + 1) for _ in range(m + 1)] # P[r][c] = sum of rows 0..r-1, columns 0..c-1
for r in range(m):
for c in range(n): # the block above and the block left both hold P[r][c]
self.P[r + 1][c + 1] = matrix[r][c] + self.P[r][c + 1] + self.P[r + 1][c] - self.P[r][c]
def sum_region(self, r1, c1, r2, c2): # the corner was taken away twice
P = self.P
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
static class NumMatrix {
private final long[][] P; // P[r][c] = sum of rows 0..r-1 and columns 0..c-1
NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
P = new long[m + 1][n + 1];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) // the block above and the block left both hold P[r][c]
P[r + 1][c + 1] = matrix[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
}
long sumRegion(int r1, int c1, int r2, int c2) { // the corner was taken away twice
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
}
class NumMatrix {
constructor(matrix) {
const m = matrix.length, n = matrix[0].length;
this.P = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)); // rows 0..r-1, columns 0..c-1
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++) // the block above and the block left both hold P[r][c]
this.P[r + 1][c + 1] = matrix[r][c] + this.P[r][c + 1] + this.P[r + 1][c] - this.P[r][c];
}
sumRegion(r1, c1, r2, c2) { // the corner was taken away twice
const P = this.P;
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
}
Each prints 8, 11, 12 and 58 for sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4) and sumRegion(0, 0, 4, 4) (the whole matrix) on Range Sum Query 2D's example, where the four numbers are row1, col1, row2, col2. The build is O(m · n); each question is four lookups, O(1).
A block around every cell
Matrix Block Sum: for every cell, the sum of the block that reaches k cells out in each direction, cut off at the edges. Build the table once, then ask it one rectangle per cell, with the rectangle clamped to the grid:
def matrix_block_sum(mat, k):
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for r in range(m):
for c in range(n):
P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
answer = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
r1, c1 = max(0, i - k), max(0, j - k) # clamp the block to the grid
r2, c2 = min(m - 1, i + k), min(n - 1, j + k)
answer[i][j] = P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
return answer
For [[1, 2, 3], [4, 5, 6], [7, 8, 9]] it prints [[12, 21, 16], [27, 45, 33], [24, 39, 28]] with k = 1 and [[45, 45, 45], [45, 45, 45], [45, 45, 45]] with k = 2 (every block covers the whole grid). O(m · n) in all, however big k is.
Both ideas at once
The two halves combine. To add 1 to many rectangles of a grid (Increment Submatrices by One), make four writes per rectangle, at its corners just past the edges, and rebuild with a 2D running total:
def range_add_queries(n, queries):
diff = [[0] * (n + 1) for _ in range(n + 1)] # one spare row and column
for r1, c1, r2, c2 in queries:
diff[r1][c1] += 1 # four corners: the 2D form of +v and -v
diff[r1][c2 + 1] -= 1
diff[r2 + 1][c1] -= 1
diff[r2 + 1][c2 + 1] += 1
mat = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
above = mat[r - 1][c] if r else 0
left = mat[r][c - 1] if c else 0
corner = mat[r - 1][c - 1] if r and c else 0
mat[r][c] = diff[r][c] + above + left - corner # a 2D running total
return mat
For a 3 × 3 grid with the rectangles [[1, 1, 2, 2], [0, 0, 1, 1]] it prints [[1, 1, 0], [1, 2, 1], [0, 1, 1]].
Spotting it
Reach for a difference array when you see:
- add v to every element from l to r, many times, then read the result once (bookings, flights, "apply these updates");
- things that start and stop at points (passengers on and off, intervals covering a point): +1 where each starts, −1 where it stops.
Reach for a 2D table when you see the sum of a rectangle, asked many times, or a block around every cell.
And the near-misses:
- reads mixed in between the updates: each read would need a fresh O(n) pass. That's a Fenwick or segment tree, in the Advanced section.
- positions up to 10^9 with few events: an array that big is mostly empty, so sort the change points instead (the sweep line in Intervals).
- the largest value in a range or rectangle: nothing to subtract, so no table of totals helps.
Common mistakes
Stopping at end instead of after it. diff[end] -= inc
The last position of every range misses its update. On 5 zeros with [[1, 3, 2], [2, 4, 3], [0, 2, -2]] it returns [-2, 0, 5, 3, 0] instead of [-2, 0, 3, 5, 3].
No spare slot. diff = [0] * length
Fine until a range reaches the last position. The same updates crash: IndexError: list index out of range. In Java it's an ArrayIndexOutOfBoundsException. Give d length + 1 slots.
Car Pooling with an inclusive end. change[stop + 1] -= passengers
Riders who are off at 5 still take up seats at 5. On [[2, 1, 5], [3, 5, 7]] with capacity 3 it returns False, though the car never holds more than 3.
Building the 2D table without taking off the overlap. matrix[r][c] + P[r][c + 1] + P[r + 1][c]
The block above-left is counted twice, and the error grows with every row. sumRegion(2, 1, 4, 3) on Range Sum Query 2D's example returns 295 instead of 8.
Clamping only one side in Matrix Block Sum. r1, c1 = i - k, j - k
Clamping the far side stops the crash, so this looks finished. But at cell (0, 0), i − k is −1, and Python reads P[-1], the table's last row, without complaint: it returns 9 instead of 12. Clamp both sides with max(0, …) and min(m − 1, …).
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Range Addition: the difference array.
- Car Pooling: the same, with riders off at
to. - Range Sum Query 2D - Immutable: build the table, answer with four totals.
- Matrix Block Sum: one clamped rectangle per cell.
Then the Prefix Sum Quiz checks the whole section.