2.3 Difference Arrays

A difference array is the inverse pattern of a prefix sum. Prefix sums make range queries fast. Difference arrays make range updates fast.

The typical problem is this: you have an array A of length n, and you need to apply many updates of the form “add x to every element from index l through index r.” Updating each element directly costs O(r - l + 1) per operation. A difference array reduces each range update to O(1), then reconstructs the final array with one prefix pass.

Problem

You need to process many range increment operations:

add x to A[l], A[l+1], ..., A[r]

A direct implementation is simple:

for i := l; i <= r; i++ {
	a[i] += x
}

This is too slow when both the array and the number of updates are large. If there are q updates, the worst case cost is O(nq).

Solution

Use an auxiliary array D of length n + 1.

For an inclusive update [l, r], do:

D[l] += x
D[r+1] -= x

After all updates are recorded, scan from left to right and maintain the running sum. That running sum is the value added to the current index.

func ApplyRangeAdds(n int, updates []Update) []int {
	d := make([]int, n+1)

	for _, u := range updates {
		d[u.L] += u.X
		d[u.R+1] -= u.X
	}

	a := make([]int, n)
	cur := 0
	for i := 0; i < n; i++ {
		cur += d[i]
		a[i] = cur
	}

	return a
}

type Update struct {
	L int
	R int
	X int
}

The extra slot at D[n] makes the operation D[r+1] -= x valid even when r == n-1.

Example

Suppose n = 6, and we apply these updates:

add 3 to [1, 3]
add 2 to [2, 5]
add 4 to [0, 0]

Record them in D:

D[1] += 3, D[4] -= 3
D[2] += 2, D[6] -= 2
D[0] += 4, D[1] -= 4

The difference array becomes:

index: 0   1   2   3   4   5   6
D:     4  -1   2   0  -3   0  -2

Now scan with a running sum:

i = 0: cur = 4
i = 1: cur = 3
i = 2: cur = 5
i = 3: cur = 5
i = 4: cur = 2
i = 5: cur = 2

Final array:

[4, 3, 5, 5, 2, 2]

Why It Works

A range update adds x starting at l and stops adding x after r.

The entry D[l] += x says: from index l onward, increase the running value by x.

The entry D[r+1] -= x says: from index r+1 onward, remove that increase.

During reconstruction, the current value is:

cur = D[0] + D[1] + ... + D[i]

So every update contributes x exactly to indices i such that:

l <= i <= r

It contributes nothing before l, because the running sum has not yet reached D[l]. It contributes nothing after r, because D[r+1] cancels it.

Invariant

During reconstruction, before assigning A[i], the variable cur satisfies:

cur = total value added by all updates whose range contains i

At each index, we first add D[i] to cur. This accounts for all updates that start or stop at i. Then we assign:

a[i] = cur

This gives the correct final value at index i.

Half-Open Interval Form

For implementation, the cleanest convention is often half-open intervals:

[l, r)

This means that l is included and r is excluded.

To add x to all indices in [l, r), do:

D[l] += x
D[r] -= x

This version avoids the r + 1 expression and matches Go slice conventions.

type HalfOpenUpdate struct {
	L int
	R int
	X int
}

func ApplyRangeAddsHalfOpen(n int, updates []HalfOpenUpdate) []int {
	d := make([]int, n+1)

	for _, u := range updates {
		d[u.L] += u.X
		d[u.R] -= u.X
	}

	a := make([]int, n)
	cur := 0
	for i := 0; i < n; i++ {
		cur += d[i]
		a[i] = cur
	}

	return a
}

For a single element at index i, use [i, i+1).

For the whole array, use [0, n).

For an empty update, use [i, i), which has no effect if implemented carefully.

Starting from an Existing Array

If the initial array is not all zero, compute its difference representation first.

For an array A:

D[0] = A[0]
D[i] = A[i] - A[i-1] for i > 0

Then range updates can be applied to D, and a prefix pass reconstructs the final array.

func Difference(a []int) []int {
	n := len(a)
	d := make([]int, n+1)

	if n == 0 {
		return d
	}

	d[0] = a[0]
	for i := 1; i < n; i++ {
		d[i] = a[i] - a[i-1]
	}

	return d
}

func Reconstruct(d []int, n int) []int {
	a := make([]int, n)
	cur := 0

	for i := 0; i < n; i++ {
		cur += d[i]
		a[i] = cur
	}

	return a
}

Example:

a := []int{5, 7, 7, 3}
d := Difference(a)

// d is [5, 2, 0, -4, 0]

The prefix sums of d recover a.

Complexity

Let n be the array length and q be the number of updates.

Direct range updates cost:

O(nq)

in the worst case.

Difference arrays cost:

O(q + n)

because each update is recorded in constant time, and the final reconstruction takes one linear pass.

Extra space is:

O(n)

Two-Dimensional Difference Arrays

The same idea works for rectangle updates in a matrix.

To add x to all cells in rows [r1, r2) and columns [c1, c2), update four corners:

D[r1][c1] += x
D[r2][c1] -= x
D[r1][c2] -= x
D[r2][c2] += x

Then reconstruct using two-dimensional prefix sums.

type RectUpdate struct {
	R1 int
	C1 int
	R2 int
	C2 int
	X  int
}

func ApplyRectAdds(rows, cols int, updates []RectUpdate) [][]int {
	d := make([][]int, rows+1)
	for i := range d {
		d[i] = make([]int, cols+1)
	}

	for _, u := range updates {
		d[u.R1][u.C1] += u.X
		d[u.R2][u.C1] -= u.X
		d[u.R1][u.C2] -= u.X
		d[u.R2][u.C2] += u.X
	}

	a := make([][]int, rows)
	for i := range a {
		a[i] = make([]int, cols)
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			up := 0
			if i > 0 {
				up = a[i-1][j]
			}

			left := 0
			if j > 0 {
				left = a[i][j-1]
			}

			diag := 0
			if i > 0 && j > 0 {
				diag = a[i-1][j-1]
			}

			a[i][j] = d[i][j] + up + left - diag
		}
	}

	return a
}

The four corner updates mark where the added value starts and where it must be canceled. The prefix reconstruction spreads the contribution across the rectangle and cancels it outside the rectangle.

Common Pitfalls

The most common error is mixing inclusive and half-open intervals. Choose one convention and keep it for the whole API.

Another common error is forgetting the extra slot. For inclusive intervals, D[r+1] must be valid. For half-open intervals, D[r] must be valid when r == n.

Difference arrays are suited to offline range updates. They work best when all updates are known before the final values are needed. If you need online range updates and online range queries, use a Fenwick tree or segment tree instead.

Integer overflow is still possible. If many large updates accumulate, use int64.

Takeaway

A difference array records where changes start and stop. Each range update becomes two assignments. A final prefix pass turns those boundary markers into actual values. Use it when you have many range updates and can reconstruct the final array after all updates are known.