Difference Array

The dual of the prefix sum: range update in $O (1)$ , then one $O (n)$ pass to recover the final array.

$add x to [l, r] : d [l] + = x, d [r + 1] - = x .$

vector<long long> d(n + 1, 0);
 
auto rangeAdd = [&](int l, int r, long long x) { d[l] += x; d[r + 1] -= x; };
 
// finalise: prefix sum recovers the array
for (int i = 1; i < n; i++) d[i] += d[i - 1];

$q$ updates and one final pass: $O (q + n)$ total, versus $O (q n)$ naively.

2D difference array

Add $x$ to the rectangle $(r_{1}, c_{1}) .. (r_{2}, c_{2})$ with four point updates:

d[r1][c1]     += x;
d[r1][c2+1]   -= x;
d[r2+1][c1]   -= x;
d[r2+1][c2+1] += x;
 
// finalise with a 2D prefix sum
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (i) d[i][j] += d[i-1][j];
        if (j) d[i][j] += d[i][j-1];
        if (i && j) d[i][j] -= d[i-1][j-1];
    }

Difference of differences

Applying the trick twice handles arithmetic progression updates — “add $1, 2, 3, \dots$ over $[l, r]$ ”:

// add an AP with first term a and common difference k over [l, r]
d[l]     += a;
d[l + 1] += k - a;
d[r + 1] -= a + (long long)(r - l) * k;      // stop the progression
d[r + 2] += a + (long long)(r - l - 1) * k;  // and cancel the slope
// then take the prefix sum TWICE

Getting the boundary terms right is fiddly; derive them by writing out a small example rather than memorising.

The difference array on a tree

Path updates without HLD. To add $x$ along the path $u \to v$ :

diff[u] += x;
diff[v] += x;
diff[lca] -= x;
if (par[lca] != -1) diff[par[lca]] -= x;

Then one DFS accumulating subtree sums gives each vertex’s final value. $O (lo g n)$ per update (for the LCA) plus $O (n)$ to finalise.

This is a genuinely important technique — it turns a large class of “add along many paths, then report all vertex values” problems into something you can write in ten lines. For edge updates, place the value on the child endpoint and subtract twice at the LCA.

When to use which

Updates	Queries	Structure
range add, all at once	read all values at the end	difference array, $O (q + n)$
range add, interleaved point queries	point	BIT on the difference array, $O (lo g n)$
range add	range sum	two BITs, or lazy segment tree
range assign / range min	anything	lazy segment tree
path add on a tree, read at the end	vertex values	tree difference array
path add on a tree, interleaved queries	path/subtree	HLD + lazy segment tree

The BIT-on-difference trick

Putting a Fenwick tree over the difference array gives range update, point query in $O (lo g n)$ with a plain BIT:

void rangeAdd(int l, int r, long long x) { bit.add(l, x); bit.add(r + 1, -x); }
long long pointGet(int i) { return bit.prefixSum(i); }

Two such BITs give range update, range query — see Fenwick Tree.

Typical uses

Booking / scheduling: “how many events overlap each moment” — $+ 1$ at the start, $- 1$ at the end
Flight bookings, hotel occupancy, traffic counting
Grid stamping: apply many rectangle increments, then read the grid
Sweep-line event accumulation
Range updates that all precede all queries — always check for this, it is the cheapest possible solution

See also: Prefix Sum · Fenwick Tree · LCA

whoashish's cp notes

Directory