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.

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.

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.

When To Use It

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