Skip to content

Difference Arrays: The Geometric Toolkit

On the previous page, you learned to see arrays as curves and describe their shape using slopes. Now let's use that lens to build one of the most practical tools in competitive programming: the difference array.

Most people learn difference arrays as a trick — "to add \(V\) to range \([L, R]\), do diff[L] += V and diff[R+1] -= V." That's the recipe, but it tells you nothing about why it works or when to reach for it. The geometric interpretation makes everything click.

Curves and Translation

Start with an array A = [3, 5, 8, 12]. Plot it. It's a curve going upward.

Now add 5 to every element: [8, 10, 13, 17]. What happened to the curve? It shifted up by 5. Same shape, same slopes — just higher. That's a translation.

Adding a constant to every element translates the curve vertically. The shape doesn't change. The slopes don't change. Only the height changes.

This is obvious, but it's the seed of something powerful. What if you don't want to shift the entire curve up? What if you only want to shift a segment of it?

The Difference Array Is Just the Slopes

Here's the key insight. Take an array and compute the differences between consecutive elements:

Array A:  [3, 5, 8, 12]
Slopes:   [3, 2, 3, 4]    (where slopes[0] = A[0] = 3)

Wait — that's the same thing as slopes. The difference array is the slope array (with the first element being \(A[0]\) itself, since there's nothing before it).

To go from the difference array back to the original: take the prefix sum.

Prefix sum of [3, 2, 3, 4] = [3, 5, 8, 12]  ✓

So here's the relationship:

  • Difference array = slopes of the original array
  • Prefix sum of the difference array = the original array back

They're inverse operations. This is the foundation everything else builds on.

Range Updates as Curve Surgery

Here's the problem: you have an array of \(N\) zeros, and you get \(Q\) queries, each saying "add \(V\) to every element from index \(L\) to \(R\)." After all queries, output the final array.

The naive approach: for each query, loop from \(L\) to \(R\) and add \(V\). That's \(O(N)\) per query, \(O(NQ)\) total. Slow.

The difference array approach: think geometrically.

What does "add V to range [L, R]" look like?

Imagine the curve of your array. Before the update, it's flat (all zeros). After adding \(V\) to \([L, R]\), the segment from \(L\) to \(R\) lifts up by \(V\) while everything else stays at 0.

Now think about what happened to the slopes:

  • At index \(L\): the curve jumps up by \(V\). The slope at \(L\) increased by \(V\).
  • From \(L+1\) to \(R\): the curve stays at the new height. No slope change.
  • At index \(R+1\): the curve drops back down by \(V\). The slope at \(R+1\) decreased by \(V\).

That's two operations on the difference array:

diff[L]   += V    // slope goes up: curve lifts here
diff[R+1] -= V    // slope goes down: curve drops back

Two operations. Constant time. Doesn't matter if the range is 10 elements or 10 million.

After processing all queries, take the prefix sum of the difference array to recover the final array. One \(O(N)\) pass at the end.

Full Example

Array size \(N = 6\) (all zeros initially). Three queries:

  1. Add 3 to range \([1, 4]\)
  2. Add 2 to range \([2, 5]\)
  3. Add 1 to range \([0, 2]\)

Build the difference array:

Query 1: diff[1] += 3,  diff[5] -= 3
Query 2: diff[2] += 2,  diff[6] -= 2    (R+1 = 6, beyond array — that's fine)
Query 3: diff[0] += 1,  diff[3] -= 1

diff = [1, 3, 2, -1, 0, -3, -2]

Prefix sum to get the final array:

prefix[0] = 1
prefix[1] = 1 + 3 = 4
prefix[2] = 4 + 2 = 6
prefix[3] = 6 + (-1) = 5
prefix[4] = 5 + 0 = 5
prefix[5] = 5 + (-3) = 2

Final array: [1, 4, 6, 5, 5, 2]

Let's verify query 1: indices 1-4 should have +3. Before other queries, that's [0, 3, 3, 3, 3, 0]. Layer on query 2 ([0, 0, 2, 2, 2, 2]) and query 3 ([1, 1, 1, 0, 0, 0]). Sum: [1, 4, 6, 5, 5, 2]. Matches.

The Code

// Process Q range-add queries on an array of size N
vector<int> rangeAdd(int n, vector<tuple<int,int,int>>& queries) {
    vector<int> diff(n + 1, 0);  // +1 for the R+1 boundary

    for (auto& [l, r, v] : queries) {
        diff[l] += v;        // slope up at L
        diff[r + 1] -= v;   // slope back down after R
    }

    // Prefix sum to recover the final array
    vector<int> result(n);
    result[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        result[i] = result[i - 1] + diff[i];
    }
    return result;
}

\(O(Q + N)\) total. Each query is \(O(1)\), and the final reconstruction is \(O(N)\).

Visualizing Slope Changes

Let's go deeper into the geometric picture, because this is what makes difference arrays intuitive rather than mechanical.

When you do diff[L] += V, you're saying: "Starting at index L, tilt the curve upward." The slope increases, so the curve rises faster from this point onward.

When you do diff[R+1] -= V, you're saying: "Starting at index R+1, tilt it back down." The slope decreases by the same amount, so the curve goes back to its original trajectory.

The net effect: the curve lifts in the range \([L, R]\) and stays flat everywhere else. That's it. Two slope changes simulate an entire range update.

This geometric view also explains why the difference array is called what it is. It stores the differences — the slope changes — and lets you reconstruct the actual values through prefix sum. You're working with the "skeleton" of the curve (its slope changes) instead of the curve itself.

Static Batch Processing

There's an important constraint: difference arrays work best when you collect all queries first, then compute the result once.

If you need the array's state after each individual query (not just at the end), the basic difference array doesn't help — you'd have to recompute the prefix sum after every update, which is back to \(O(NQ)\).

For that scenario, you'd need heavier tools: a Binary Indexed Tree (Fenwick Tree) or Segment Tree for dynamic range updates. Or for intermediate complexity, square root decomposition can handle it.

But for the common case — "here are \(Q\) updates, give me the final result" — difference arrays are perfect. Fast, simple, no data structure overhead.

Higher-Order: Arithmetic Progression Updates

What if instead of adding a constant to a range, you want to add an arithmetic progression? Like adding [3, 6, 9, 12] to indices \([2, 5]\).

The values being added aren't constant — they increase by 3 each step. A single difference array can't handle this directly, because diff[L] += V, diff[R+1] -= V only works for constant \(V\) across the range.

The Two-Layer Trick

Think about what's happening to the slopes. If we're adding [3, 6, 9, 12], the differences of what we're adding are [3, 3, 3, 3] — that's constant. So the thing we're adding has constant slopes.

A constant slope in the first difference array means a constant value in the second difference array (the difference of differences).

So we need two layers:

  • D1 (first difference array): tracks changes to the original array's slopes
  • D2 (second difference array): tracks changes to D1's slopes

To add an arithmetic progression starting at value \(S\) with step \(D\) over range \([L, R]\):

D2[L]     += D        // start the slope of the progression
D2[R+1]   -= D        // stop the slope after the range

D1[L]     += S        // initial value of the progression
D1[R+1]   -= S + D * (R - L + 1)  // undo the accumulated value + slope

This is trickier to get right. The core idea: D2 generates D1 (via prefix sum), and D1 generates the final array (via another prefix sum). Two layers of prefix sums reconstruct the array from the "skeleton of the skeleton."

General Pattern

  • Constant update over range: 1 difference array (D1)
  • Linear (AP) update over range: 2 difference arrays (D1 + D2)
  • Quadratic update over range: 3 difference arrays (D1 + D2 + D3)
  • In general, a polynomial of degree \(k\): you need \(k+1\) layers

In practice, you'll almost always use 1 or 2 layers. Three or more is rare outside of competitive programming.

Handling Huge Arrays (N = 10^9)

What if the array size is enormous — say \(10^9\) — but you only have a few thousand queries?

You can't allocate an array of size \(10^9\). But here's the thing: the difference array only has non-zero values at the \(L\) and \(R+1\) positions from your queries. With \(Q\) queries, that's at most \(2Q\) interesting positions.

Solution: use a hash map instead of an array.

map<int, long long> diff;  // sparse difference array

for (auto& [l, r, v] : queries) {
    diff[l] += v;
    diff[r + 1] -= v;
}

// Iterate in sorted order to compute prefix sums
long long running = 0;
for (auto& [pos, delta] : diff) {
    running += delta;
    // 'running' is the value at position 'pos'
}

The sorted iteration of std::map gives you the positions in order, and you accumulate the prefix sum as you go. Only \(O(Q \log Q)\) time, regardless of how large \(N\) is.

This is a pattern you'll see in coordinate compression problems. The array might be conceptually infinite, but only a finite number of "interesting" positions matter.

Connecting Back to Shape

Here's why difference arrays belong on a page about monotonicity and convexity, not just "range update tricks."

The difference array is the slope array. When you manipulate the difference array, you're directly manipulating the shape of the curve.

  • Adding a constant to a range? You're creating a "plateau" — the curve lifts flat.
  • Adding an increasing progression? You're creating a "ramp" — the curve tilts upward in that range.
  • The final prefix sum reconstructs the curve from its slope changes.

And this connects directly to how we defined convexity and concavity on the previous page. A convex function has increasing slopes. A concave function has decreasing slopes. The difference array literally stores those slopes. So when you look at a difference array and see its values going up, you're looking at a convex curve. When they go down, concave.

This isn't just a nice mental model. It's how you'll reason about DP optimizations later: "Is my DP's cost function convex? Let me look at the differences. Are they increasing? If so, I can use Slope Trick / CHT / etc."

Practice Problems

Warm-Up (Basic Difference Array)

  1. 1109. Corporate Flight Bookings — Direct application. Range add, then prefix sum.
  2. 370. Range Addition (Premium) — Same pattern, slightly different input format.
  3. 1094. Car Pooling — Passengers board and exit at different stops. Difference array on a timeline.

Core Practice

  1. 995. Minimum Number of K Consecutive Bit Flips — Greedy + difference array to track flip effects.
  2. 1589. Maximum Sum Obtained of Any Permutation — Use difference array to count how often each index is queried, then greedily assign largest values to most-queried positions.
  3. 2381. Shifting Letters II — Range shift operations on characters. Difference array on the shift amounts.

Harder

  1. 798. Smallest Rotation with Highest Score — Each element contributes a range of "good" rotations. Difference array counts total good scores per rotation.
  2. Arithmetic Progression Range Update (custom) — Given \(Q\) queries each adding an AP to a range, compute the final array. Practice the two-layer technique.

Solutions

1. Corporate Flight Bookings

Each booking [first, last, seats] is a range add.

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> diff(n + 1, 0);
    for (auto& b : bookings) {
        diff[b[0] - 1] += b[2];     // 1-indexed → 0-indexed
        diff[b[1]] -= b[2];
    }
    vector<int> ans(n);
    ans[0] = diff[0];
    for (int i = 1; i < n; ++i)
        ans[i] = ans[i - 1] + diff[i];
    return ans;
}
3. Car Pooling

Passengers get on at from and off at to. This is a range add of numPassengers on [from, to). Check if the running sum ever exceeds capacity.

bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> diff(1001, 0);
    for (auto& t : trips) {
        diff[t[1]] += t[0];     // board at 'from'
        diff[t[2]] -= t[0];     // exit at 'to'
    }
    int current = 0;
    for (int i = 0; i < 1001; ++i) {
        current += diff[i];
        if (current > capacity) return false;
    }
    return true;
}
4. Minimum K Consecutive Bit Flips

Greedy: scan left to right. If current element is 0 (after flips), flip the next K elements. Use a difference array to track active flips instead of actually flipping.

int minKBitFlips(vector<int>& nums, int k) {
    int n = nums.size(), flips = 0, currentFlips = 0;
    vector<int> flipEnd(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        currentFlips += flipEnd[i];
        // After accounting for flips, is this bit 0?
        if ((nums[i] + currentFlips) % 2 == 0) {
            if (i + k > n) return -1;  // can't flip K from here
            flips++;
            currentFlips++;
            flipEnd[i + k]--;  // this flip expires after K positions
        }
    }
    return flips;
}
5. Maximum Sum Obtained of Any Permutation

Count how many queries include each index (difference array). Sort the counts. Sort the array. Multiply largest values with most-queried positions.

int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
    int n = nums.size();
    vector<int> diff(n + 1, 0);
    for (auto& r : requests) {
        diff[r[0]]++;
        diff[r[1] + 1]--;
    }
    // Prefix sum to get frequency of each index
    vector<int> freq(n);
    freq[0] = diff[0];
    for (int i = 1; i < n; ++i) freq[i] = freq[i - 1] + diff[i];

    sort(freq.begin(), freq.end());
    sort(nums.begin(), nums.end());

    long long ans = 0, mod = 1e9 + 7;
    for (int i = 0; i < n; ++i)
        ans = (ans + (long long)freq[i] * nums[i]) % mod;
    return ans;
}
6. Shifting Letters II

Each query shifts a range of characters forward or backward. Difference array accumulates the total shift per index.

string shiftingLetters(string s, vector<vector<int>>& shifts) {
    int n = s.size();
    vector<int> diff(n + 1, 0);
    for (auto& sh : shifts) {
        int val = (sh[2] == 1) ? 1 : -1;
        diff[sh[0]] += val;
        diff[sh[1] + 1] -= val;
    }
    int running = 0;
    for (int i = 0; i < n; ++i) {
        running += diff[i];
        int shift = ((running % 26) + 26) % 26;  // handle negative
        s[i] = 'a' + (s[i] - 'a' + shift) % 26;
    }
    return s;
}

What's Next

You now have the geometric lens (shapes via slopes) and the practical tool (difference arrays as slope manipulation). The next page — When Shapes Survive: Function Addition — answers the big question: "If I add two functions together, does the resulting function keep its shape?" The answer to that question is the foundation for every DP optimization technique in competitive programming.