Skip to content

Difference Arrays

A difference array (or difference / imos trick) stores the changes between consecutive positions. It lets you apply range add updates in \(O(1)\) each and recover the final array with one pass.

Pair it with Prefix Arrays: difference is the inverse flavor—good for many updates, prefix sums for many queries on a fixed array.

Idea

For an array a, define diff so that diff[0] = a[0] and diff[i] = a[i] - a[i-1] for i > 0. Then a is the prefix sum of diff.

To add v to every index in \([l, r]\) (inclusive):

  • diff[l] += v
  • diff[r + 1] -= v (if r + 1 exists)

After all updates, reconstruct a by scanning: a[i] = a[i-1] + diff[i].

Implementation

#include <vector>
using namespace std;

void rangeAdd(vector<int>& diff, int l, int r, int v) {
    diff[l] += v;
    if (r + 1 < (int)diff.size()) diff[r + 1] -= v;
}

vector<int> reconstruct(const vector<int>& diff) {
    int n = (int)diff.size();
    vector<int> a(n);
    a[0] = diff[0];
    for (int i = 1; i < n; i++) a[i] = a[i - 1] + diff[i];
    return a;
}

Initialize diff with size n (or n+1 with a sentinel at the end if you only use range adds on an initially zero array).

Example

Start from zeros: diff all zero. Apply “add 5 to \([1,3]\)” on length 5:

  • After rangeAdd(diff, 1, 3, 5): reconstruct → [0, 5, 5, 5, 0].

Multiple range updates

Apply each update with rangeAdd. Reconstruct once at the end when you need the actual values.

void applyUpdates(vector<int>& diff, const vector<tuple<int,int,int>>& updates) {
    for (auto& t : updates) {
        int l, r, v;
        tie(l, r, v) = t;
        rangeAdd(diff, l, r, v);
    }
}

2D difference

For rectangle adds on a grid, use a 2D difference array with four corner updates; then 2D prefix to get final cells. Same “difference then prefix” pattern.

Complexity

  • One range update: \(O(1)\)
  • Reconstruct length \(n\): \(O(n)\)
  • Space: \(O(n)\)