Difference Array

A difference array represents changes between neighboring positions. It makes repeated range updates efficient.

Instead of updating every value in a range immediately, the algorithm marks where the change starts and where it stops.

Core Idea

To add x to every value from left to right, add x at left and subtract x just after right. A final prefix sum over the difference array reconstructs the updated values.

This is useful when all updates are known before the final values are needed.

Function Contract

apply_range_updates(size, updates) expects size to be the final array length and updates to contain (left, right, amount) triples.

Each update uses inclusive indexes and adds amount to every position from left through right. The function returns the final array after all updates are applied.

Python Example

def apply_range_updates(size, updates):
    diff = [0] * (size + 1)
 
    for left, right, amount in updates:
        diff[left] += amount
        diff[right + 1] -= amount
 
    result = []
    running = 0
    for i in range(size):
        running += diff[i]
        result.append(running)
 
    return result

Each range update is recorded in constant time.

Step-by-Step Example

Suppose an array of size 5 starts as all zeros, and the update is “add 3 from index 1 through index 3.”

The difference array records:

diff[1] += 3
diff[4] -= 3

Accumulating the difference gives:

[0, 3, 3, 3, 0]

The +3 starts at index 1, and the -3 stops it after index 3.

Why It Works

The accumulated difference array carries each update forward until a later boundary cancels it. A range update becomes two boundary changes.

Complexity

Each update is recorded in O(1). Reconstructing the final array is O(n). For q updates, the total time is O(n + q).

Common Confusions

A difference array is not the final array. It must be accumulated to recover actual values.

The extra slot at size is often used so right + 1 can be updated safely when the range reaches the last real index.

Difference arrays are usually offline. If the problem asks for queries between updates, a Fenwick tree or segment tree may be more appropriate.

When To Use It

Use a difference array when many range additions are applied first and the final array is needed afterward.

Do not use it when each update must be visible immediately to future range queries unless the problem structure still allows batching.

The Main Point

A difference array turns a range update into two boundary changes, then reconstructs the final values with one prefix pass.