Lesson 8 · Linear structures

Difference Arrays

A difference array is the inverse of a prefix sum array. It is used when you need to add a value to a large range of elements multiple times. Instead of looping over the range, you mark the start and end of the change in O(1) time.

The Range Update Problem

Imagine you have an array of zeroes and you are given 100,000 commands like 'add 5 to all elements from index 2 to 8'.

Looping from index 2 to 8 for every command takes O(N) per query, which is too slow for large data. We need a way to apply updates in O(1) time.

Naive range updates are O(N)
Multiple updates lead to O(Q * N) complexity
Difference arrays solve this specific bottleneck

Creating the Marks

Instead of updating every element, we create a difference array D. To add V to the range [L, R], we only make two modifications.

We add V to D[L] (meaning 'start adding V from here onward') and subtract V from D[R+1] (meaning 'stop adding V from this point onward').

D[L] += V starts the effect
D[R+1] -= V ends the effect
Only two elements are touched per update

Key reference

Terms, operations, and practical uses

Core operations

Range AdditionAdding a specific value V to every element between an arbitrary start index L and end index R.
Point UpdateModifying only specific boundary indices (L and R+1) to represent a bulk change, requiring strictly O(1) time.
ReconstructionRunning a prefix sum pass over a difference array to calculate the final values of all elements.

State and timing

Offline QueriesProcessing all modifications first, and only asking for the final answers after all updates are complete.
Online QueriesInterleaving updates and queries (e.g., Update, Query, Update). Difference arrays fail here because reconstruction takes O(N).
Sweep LineA broader algorithmic paradigm closely related to difference arrays, where events are processed in sorted order from left to right.

Use cases

Interval OverlapCounting how many intervals overlap at any given point by adding 1 at the start and subtracting 1 after the end.
Flight BookingsA classic problem: applying capacity changes across a range of flight segments efficiently.
2D Difference ArrayAdding a value to a 2D subgrid by placing four marks (start, end-right, end-down, end-diagonal) and running a 2D prefix sum.

Code example

Applying Range Updates via Difference Array

N = 5
D = [0] * (N + 1)

# Add 10 to [1, 3]
D[1] += 10
D[3+1] -= 10

# Subtract 5 from [2, 4]
D[2] -= 5
if 4+1 <= N:
    D[4+1] += 5

# Reconstruct
A = [0] * N
current = 0
for i in range(N):
    current += D[i]
    A[i] = current

print('Final array:', A)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N = 5;
    vector<int> D(N + 1, 0);

    // Add 10 to [1, 3]
    D[1] += 10;
    D[3+1] -= 10;

    // Subtract 5 from [2, 4]
    D[2] -= 5;
    if (4+1 <= N) D[4+1] += 5;

    // Reconstruct
    vector<int> A(N, 0);
    int current = 0;
    for (int i = 0; i < N; i++) {
        current += D[i];
        A[i] = current;
    }
    return 0;
}

class Main {
    public static void main(String[] args) {
        int N = 5;
        int[] D = new int[N + 1];

        // Add 10 to [1, 3]
        D[1] += 10;
        D[4] -= 10;

        // Subtract 5 from [2, 4]
        D[2] -= 5;
        if (5 <= N) D[5] += 5;

        // Reconstruct
        int[] A = new int[N];
        int current = 0;
        for (int i = 0; i < N; i++) {
            current += D[i];
            A[i] = current;
        }
    }
}

InputArray of 5 zeros. Add 10 to [1,3], subtract 5 from [2,4]

OutputFinal array: [0, 10, 5, 5, -5]

Example

Run the example step by step

Output

Reconstructing the Array

After applying all range update commands to D in O(1) time each, we must reconstruct the actual array values.

We do this by running a prefix sum on the difference array. As we scan left to right, we accumulate the values. The accumulated sum at index i is the final value of the array at i.

Reconstruction requires one O(N) pass
Total time is O(Q + N)
Brilliant combination of two patterns

When to Use

Difference arrays are strictly for offline range updates. This means you must process all updates first, before you need to read any of the final values.

If you need to query values interleaved between updates, a difference array cannot reconstruct the array fast enough. You would need a Segment Tree or Fenwick Tree instead.

Perfect for offline updates
Common in scheduling and interval overlap problems
Not suitable for mixed update/query scenarios