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
}