Difference Array

A difference array stores how each element changes from the previous element. It lets you apply range additions in constant time and reconstruct the final array with a prefix sum.

You use it when many range updates are applied before the final values are needed.

Problem

Given an array $A$ of length $n$ , support range updates of the form:

A[i] = A[i] + x

for every index $i$ where:

l \le i \le r

Structure

Define a difference array $D$ such that:

D[0] = A[0]

and for $i > 0$ :

D[i] = A[i] - A[i - 1]

To add $x$ over range $[l, r]$ :

add $x$ to $D[l]$
subtract $x$ from $D[r + 1]$ if $r + 1 < n$

Algorithm

Build the difference array:

build_difference(A):
    n = length(A)
    D[0] = A[0]
    for i from 1 to n - 1:
        D[i] = A[i] - A[i - 1]
    return D

Apply a range addition:

range_add(D, l, r, x):
    D[l] += x
    if r + 1 < length(D):
        D[r + 1] -= x

Reconstruct the array:

reconstruct(D):
    A[0] = D[0]
    for i from 1 to length(D) - 1:
        A[i] = A[i - 1] + D[i]
    return A

Example

Let

A = [8, 3, 5, 1, 9]

The difference array is:

D = [8, -5, 2, -4, 8]

Add $4$ to range $[1, 3]$ :

D[1] = -1

and

D[4] = 4

So:

D = [8, -1, 2, -4, 4]

Reconstruct:

index	prefix sum	value
0	8	8
1	7	7
2	9	9
3	5	5
4	9	9

Result:

[8, 7, 9, 5, 9]

Correctness

The difference array records where value changes begin and end. Adding $x$ at $D[l]$ increases every reconstructed value from index $l$ onward. Subtracting $x$ at $D[r + 1]$ cancels that increase after index $r$ . Therefore, only indices in $[l, r]$ receive the update.

Reconstruction by prefix sums restores the original values plus all encoded updates.

Complexity

operation	time
build	$O(n)$
range add	$O(1)$
reconstruct	$O(n)$

Space usage:

O(n)

When to Use

Difference arrays are appropriate when:

many range updates are known before queries
final values are needed after all updates
updates are additive
the array can be reconstructed in one pass

They are less suitable when range queries must be answered between updates. In that case, use a Fenwick tree or segment tree.

Implementation

def build_difference(a):
    if not a:
        return []

    d = [0] * len(a)
    d[0] = a[0]

    for i in range(1, len(a)):
        d[i] = a[i] - a[i - 1]

    return d

def range_add(d, l, r, x):
    d[l] += x
    if r + 1 < len(d):
        d[r + 1] -= x

def reconstruct(d):
    if not d:
        return []

    a = [0] * len(d)
    a[0] = d[0]

    for i in range(1, len(d)):
        a[i] = a[i - 1] + d[i]

    return a

func BuildDifference(a []int) []int {
    if len(a) == 0 {
        return nil
    }

    d := make([]int, len(a))
    d[0] = a[0]

    for i := 1; i < len(a); i++ {
        d[i] = a[i] - a[i-1]
    }

    return d
}

func RangeAdd(d []int, l, r, x int) {
    d[l] += x
    if r+1 < len(d) {
        d[r+1] -= x
    }
}

func Reconstruct(d []int) []int {
    if len(d) == 0 {
        return nil
    }

    a := make([]int, len(d))
    a[0] = d[0]

    for i := 1; i < len(d); i++ {
        a[i] = a[i-1] + d[i]
    }

    return a
}