Pattern Guide
Difference Array & Range Updates
"Add delta to range [l,r] in O(1). Prefix sum to recover. Sweep line in 1D."
A difference array enables O(1) range updates: to add delta to all elements in [l, r], write diff[l] += delta and diff[r+1] -= delta. After all updates, prefix sum the diff array to get the final values. This technique also models "events at endpoints" for sweep-line problems. 2D difference arrays extend this to rectangles.
Problems you can solve with this pattern
5 problems · click any to start solving
// 1D difference array
class DifferenceArray {
constructor(n) { this.diff = new Array(n + 2).fill(0); }
add(l, r, v) { this.diff[l] += v; this.diff[r + 1] -= v; }
build() {
const arr = [...this.diff];
for (let i = 1; i < arr.length; i++) arr[i] += arr[i - 1];
return arr;
}
}
// 2D difference array for rectangle range updates
class DiffArray2D {
constructor(m, n) { this.d = Array.from({length:m+2},()=>new Array(n+2).fill(0)); }
add(r1, c1, r2, c2, v) {
this.d[r1][c1] += v;
this.d[r1][c2+1] -= v;
this.d[r2+1][c1] -= v;
this.d[r2+1][c2+1] += v;
}
build() {
const m = this.d.length, n = this.d[0].length;
for (let i = 0; i < m; i++) for (let j = 1; j < n; j++) this.d[i][j] += this.d[i][j-1];
for (let j = 0; j < n; j++) for (let i = 1; i < m; i++) this.d[i][j] += this.d[i-1][j];
return this.d;
}
}
// Event-based sweep (coordinate-compressed difference array)
// For ranges [l1,r1], [l2,r2], ... with values v1, v2:
// events = [{pos: l, +v}, {pos: r+1, -v}]
// Sort events by pos, sweep to get value at each pointDifference array converts "range update, point query" into "point update, prefix query." The diff array stores delta changes: diff[i] = arr[i] - arr[i-1]. To add v to arr[l..r]: diff[l] += v and diff[r+1] -= v. After all updates, prefix sum diff to recover arr. When combined with coordinate compression, this handles sparse ranges up to 10^9.
// 1D difference array
class DifferenceArray {
constructor(n) { this.diff = new Array(n + 2).fill(0); }
add(l, r, v) { this.diff[l] += v; this.diff[r + 1] -= v; }
build() {
const arr = [...this.diff];
for (let i = 1; i < arr.length; i++) arr[i] += arr[i - 1];
return arr;
}
}
// 2D difference array for rectangle range updates
class DiffArray2D {
constructor(m, n) { this.d = Array.from({length:m+2},()=>new Array(n+2).fill(0)); }
add(r1, c1, r2, c2, v) {
this.d[r1][c1] += v;
this.d[r1][c2+1] -= v;
this.d[r2+1][c1] -= v;
this.d[r2+1][c2+1] += v;
}
build() {
const m = this.d.length, n = this.d[0].length;
for (let i = 0; i < m; i++) for (let j = 1; j < n; j++) this.d[i][j] += this.d[i][j-1];
for (let j = 0; j < n; j++) for (let i = 1; i < m; i++) this.d[i][j] += this.d[i-1][j];
return this.d;
}
}
// Event-based sweep (coordinate-compressed difference array)
// For ranges [l1,r1], [l2,r2], ... with values v1, v2:
// events = [{pos: l, +v}, {pos: r+1, -v}]
// Sort events by pos, sweep to get value at each point- All updates first, then one final read → diff array O(n+k)
- Segment tree: O(k log n) updates + O(n) read — more overhead
2D difference array: add v to rectangle [r1,c1]→[r2,c2]:
- diff[r1][c1] += v
- diff[r1][c2+1] -= v
- diff[r2+1][c1] -= v
- diff[r2+1][c2+1] += v
Then double prefix sum to recover.
Coordinate-compressed event sweep: when positions are huge (up to 10^9) but few (≤ 10^5), sort events, use a map as the diff array.