# Difference Array

# 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:

```id="difference-build"
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:

```id="difference-range-add"
range_add(D, l, r, x):
    D[l] += x
    if r + 1 < length(D):
        D[r + 1] -= x
```

Reconstruct the array:

```id="difference-reconstruct"
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

```python id="difference-python"
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
```

```go id="difference-go"
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
}
```