Difference Arrays

A difference array is the discrete inverse of a prefix sum array: where the prefix sum encodes “running total at each position,” the difference array encodes “change between consecutive positions.” This dual representation flips the cost model. A plain array supports O(1) point updates and O(n) range queries; a prefix-sum array supports O(n) point updates (because every cell to the right shifts) but O(1) range sum queries; a difference array supports O(1) range updates (add v to every position in [l, r]) but only delivers final values after an O(n) reconstruction sweep. The pattern is the canonical answer when a problem applies many range increments and only asks for the final state at the end. Combined with prefix sums, it forms the building block for the offline range-update + range-query solution that beats segment trees in simplicity for problems where all updates can be batched before the queries.

1. Intuition — Marking the Edges, Not the Interior

Imagine you’re a city planner allocating bike-share docks across a 1-kilometer street, position by meter (positions 0 through 999). Three contractors send you orders:

• “Add 5 docks to every meter from 100 to 300.”
• “Add 3 docks to every meter from 250 to 600.”
• “Add 7 docks to every meter from 50 to 200.”

The naive approach: walk every meter in each range and increment a counter. Three orders covering 200, 350, and 150 meters respectively — 700 individual writes for three logical updates.

The difference-array approach: at the start of each range write +v; at the position immediately after the end of each range write -v. The first contractor’s order becomes diff[100] += 5; diff[301] -= 5. Two writes per order, regardless of range length. After all orders are recorded, you sweep the difference array from left to right accumulating a running sum, and that running sum at position i is the final dock count at meter i.

The key insight is that the running sum at position i automatically incorporates every range that started at or before i and hasn’t yet ended. The +5 at position 100 turns on a “this range contributes +5” flag; the running sum carries that contribution forward to positions 101, 102, …, until the -5 at position 301 turns it off. You’ve encoded the boundary events of each range and let the prefix-sum sweep do the integration for you.

The mathematical analogy is sharp: prefix sums are discrete integration (S[i] = Σ_{k=0..i} arr[k]); difference arrays are discrete differentiation (D[i] = arr[i] - arr[i-1]). The fundamental theorem of calculus has a discrete echo: applying the difference operator and then the prefix-sum operator returns the original array. Range update on the original = point update on the difference. Range query on the original = point difference of the prefix sum.

2. Tiny Worked Example

Start with arr = [0, 0, 0, 0, 0, 0, 0, 0] (length 8). Apply three updates:

• update(1, 3, +5) — add 5 to positions 1, 2, 3
• update(2, 5, +2) — add 2 to positions 2, 3, 4, 5
• update(0, 7, +1) — add 1 to every position

Naive approach. Walk each range, write each cell. Total writes: 3 + 4 + 8 = 15.

Difference-array approach. Maintain diff of length 9 (one extra slot to hold the closing -v at position r + 1). Record only boundary events:

Update	Effect on diff	diff after update
init	—	[0, 0, 0, 0, 0, 0, 0, 0, 0]
(1, 3, +5)	diff[1] += 5; diff[4] -= 5	[0, +5, 0, 0, -5, 0, 0, 0, 0]
(2, 5, +2)	diff[2] += 2; diff[6] -= 2	[0, +5, +2, 0, -5, 0, -2, 0, 0]
(0, 7, +1)	diff[0] += 1; diff[8] -= 1	[+1, +5, +2, 0, -5, 0, -2, 0, -1]

Total writes for three updates: 6 (two per update). Now reconstruct the final arr by taking the prefix sum of diff (ignoring the extra slot):

i	diff[i]	running sum = arr[i]
0	+1	1
1	+5	6
2	+2	8
3	0	8
4	-5	3
5	0	3
6	-2	1
7	0	1

So arr = [1, 6, 8, 8, 3, 3, 1, 1]. Cross-check by hand: position 3 received +1 (from update 3) and +5 (from update 1) and +2 (from update 2) = 8. ✓ Position 6 received +1 (from update 3) only = 1. ✓ The difference-array approach got the same answer as the naive approach using 6 writes plus an O(n) reconstruction pass — a total of 6 + 8 = 14 operations for this tiny example, but for k updates over an array of length n, the count is 2k + n operations vs. naïve O(k × n). As soon as k gets large (say, 10⁵ updates over a 10⁵-length array), the difference becomes 10¹⁰ vs. ~3 × 10⁵ — five orders of magnitude.

3. The Pattern Recognition Signal

Reach for difference arrays when:

1. The problem applies many range updates (add v to every position in [l, r]), where the number of updates k is comparable to or larger than the array length n.
2. All updates are known in advance, or queries only happen after all updates are batched. Difference arrays are an offline technique — you record updates, then reconstruct once. If updates and point queries are interleaved, you need a Segment Tree with Lazy Propagation instead.
3. The update operation is “addition” (or any commutative, associative, easily-invertible operation) — extends to subtraction, XOR, multiplication on rings without zero divisors. Does not extend to operations like max(a, range_value) because there’s no boundary “switch” that turns the update off cleanly.
4. The problem mentions “interval increment,” “range update,” “booking,” “passengers boarding/leaving,” “airport check-ins by time window.” Anything where events have a start and an end, and you want a count or sum at every position.

The classic LeetCode triggers:

• Car pooling (LC 1094): a list of (num_passengers, start_stop, end_stop) trips; can the car (capacity C) handle them all? Difference array indexed by stop, increment at start, decrement at end.
• Corporate flight bookings (LC 1109): a list of (first_flight, last_flight, num_seats) bookings; how many seats per flight? Same shape exactly.
• Range addition (LC 370): apply k updates of the form (start, end, val) to a length-n array, return the final array. Textbook.

The inverse signal — when not to use difference arrays:

• Range-min or range-max updates. No clean inverse; falls back to segment tree.
• Online updates with interleaved queries that need point or range values before all updates are known. The difference array would need to be reconstructed after every update batch; you’ve lost the batching advantage.
• Sparse arrays where n is enormous (e.g., n = 10⁹). The difference array is still O(n) memory; you need coordinate compression first, or a different data structure (interval tree, sweep-line with sorted events).

4. Pseudocode

4.1 Range Update, Point Query (After All Updates)

diff_init(n):
    diff := array of n + 1 zeros          # one extra slot for the boundary

range_update(diff, l, r, v):              # add v to original arr[l..r] inclusive
    diff[l]     := diff[l] + v
    diff[r + 1] := diff[r + 1] - v

reconstruct(diff, n):
    arr := array of n zeros
    arr[0] := diff[0]
    for i in 1 .. n - 1:
        arr[i] := arr[i - 1] + diff[i]
    return arr

4.2 Range Update, Range Sum Query (Difference + Prefix Sum)

If you want range-sum queries after all updates, do two passes: first reconstruct the array from the difference array (one prefix-sum sweep), then build a prefix-sum array on top of the reconstruction (a second prefix-sum sweep). Range-sum query is then O(1).

build(diff, n):
    arr := reconstruct(diff, n)
    prefix := array of n + 1 zeros
    for i in 1 .. n:
        prefix[i] := prefix[i - 1] + arr[i - 1]
    return prefix

range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

Total: O(k) update cost (k updates), O(n) build cost, O(1) per query. This is what makes difference arrays the right tool for batched offline range-update + range-query — beating a segment tree’s O(log n) per update and per query for the overall workload as long as updates can be deferred until after all queries are known (or vice versa).

5. Python Implementation

5.1 The Core Pattern

class DifferenceArray:
    def __init__(self, n: int):
        self.n = n
        self.diff = [0] * (n + 1)              # n + 1 to hold the closing −v safely
 
    def update(self, l: int, r: int, v: int) -> None:
        """Add v to original[l..r] (inclusive). O(1)."""
        self.diff[l] += v
        if r + 1 < len(self.diff):
            self.diff[r + 1] -= v
 
    def reconstruct(self) -> list[int]:
        """Materialize the final array. O(n)."""
        arr = [0] * self.n
        running = 0
        for i in range(self.n):
            running += self.diff[i]
            arr[i] = running
        return arr

The single-pass reconstruction maintains the running sum directly, avoiding a separate prefix-sum array.

5.2 LC 1094 — Car Pooling

def car_pooling(trips: list[list[int]], capacity: int) -> bool:
    """trips[i] = [num_passengers, start_stop, end_stop_exclusive].
    Return True iff a car of given capacity can satisfy all trips."""
    diff = [0] * 1001                          # stops are in [0, 1000]
    for n_pass, start, end in trips:
        diff[start] += n_pass                  # passengers board at start
        diff[end]   -= n_pass                  # passengers leave at end (exclusive)
    load = 0
    for d in diff:
        load += d
        if load > capacity:
            return False
    return True

Note the choice of indexing convention. LC 1094 specifies end as the destination stop — passengers occupy seats during [start, end), leaving exactly at end. So the decrement goes at index end, not end + 1. Compare with the inclusive-end convention in §4.1 (diff[r + 1] -= v); the subtraction position depends on whether the range’s end is inclusive or exclusive in the problem statement. Read the problem text carefully — getting this off by one produces an answer that’s wrong only at the boundary stop, which is exactly the kind of bug that passes the small examples and fails the hidden tests.

5.3 LC 1109 — Corporate Flight Bookings

def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
    """bookings[i] = [first_flight, last_flight, num_seats] (1-indexed, inclusive).
    Return per-flight seat counts."""
    diff = [0] * (n + 1)                       # extra slot for the closing decrement
    for first, last, seats in bookings:
        diff[first - 1] += seats               # convert to 0-indexed
        if last < n:
            diff[last] -= seats                # 0-indexed exclusive end
    answer = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        answer[i] = running
    return answer

The 1-indexed-inclusive convention in the problem becomes a 0-indexed-half-open convention internally: a booking (first, last, seats) translates to “increment at first - 1, decrement at last” — because arr[first - 1 .. last - 1] (0-indexed inclusive) is the same as arr[first - 1 .. last) (0-indexed half-open).

6. Complexity

Per-update time: O(1). A range update touches exactly two positions in the difference array regardless of range width. This is the entire point.

Reconstruction time: O(n). A single prefix-sum sweep over the difference array.

Total cost for k updates and one final reconstruction: O(k + n). Compare with the naive approach: O(k × n) in the worst case if every range spans the whole array. The crossover point is k = log n — beyond that, difference arrays dominate.

Space: O(n). The difference array is n + 1 cells; reconstruction returns a length-n array. Could be done in place (overwrite the difference array with the prefix sum during the sweep) for a constant-factor improvement.

Comparison with segment tree. A Segment Tree with Lazy Propagation supports interleaved updates and queries in O(log n) per operation. For k updates and q queries, segment tree is O((k + q) log n); difference arrays are O(k + n + q) (after reconstruction; q queries cost O(1) each via prefix sums on top). Difference arrays win when k + q is large and you can defer reconstruction until after all updates. Segment trees win when the operations interleave or when n is much larger than k + q.

7. Two-Dimensional Difference Arrays

The pattern generalizes to 2D for problems involving rectangle increments — e.g., “add v to every cell in submatrix [(r1, c1), (r2, c2)].”

The 2D analog uses four boundary increments per update (the inclusion-exclusion rectangle corners):

update(diff, r1, c1, r2, c2, v):
    diff[r1][c1]         += v
    diff[r1][c2 + 1]     -= v
    diff[r2 + 1][c1]     -= v
    diff[r2 + 1][c2 + 1] += v

Reconstruction is a 2D prefix sum: first sweep each row left-to-right accumulating, then each column top-to-bottom accumulating. The result at every cell is the sum of all rectangle updates whose ranges contain that cell.

def apply_2d(diff: list[list[int]]) -> list[list[int]]:
    R, C = len(diff), len(diff[0])
    # row-wise prefix
    for r in range(R):
        for c in range(1, C):
            diff[r][c] += diff[r][c - 1]
    # column-wise prefix
    for c in range(C):
        for r in range(1, R):
            diff[r][c] += diff[r - 1][c]
    return diff

The four-corner trick is the discrete 2D analog of integration over a rectangle by the rule

∫∫_R f = F(r2, c2) − F(r1 − 1, c2) − F(r2, c1 − 1) + F(r1 − 1, c1 − 1)

(the ”+” on the doubly-subtracted corner is the inclusion-exclusion correction). The same shape appears in Prefix Sums §5 for 2D range queries; here it’s used in reverse — to encode a rectangle update, not to query a rectangle sum.

3D and higher generalize to 2^d corners per update; in practice 1D and 2D are the ones that show up in interviews.

8. Variants and Sub-patterns

8.1 Difference Arrays for Range Multiply / Modular Increments

Multiplication composes (multiplicative groups): a difference array can encode “multiply everything in [l, r] by v” by recording diff[l] *= v and diff[r + 1] *= 1/v (mod p, if working modular). The reconstruction sweep multiplies running. Same idea, different operation. Constraint: the operation’s inverse must exist on every value, ruling out modular arithmetic with non-coprime moduli.

8.2 Sweep-Line Algorithms

The 1D difference array generalizes to event-based sweep lines in computational geometry. Each interval contributes a +1 event at its start and a −1 event at its end; a sweep through events sorted by position computes the maximum number of overlapping intervals (the intersection number) — the same mechanic as LC 1094 car-pooling, applied to time windows or geometric intervals. The sweep-line idea scales to 2D for problems like “find the most-attended hour at a conference” or “compute the area of the union of rectangles.”

8.3 Imos Method (いもす法)

The “Imos method” (named after Japanese competitive-programmer “imos”) is the same idea as difference arrays, taught widely in Japanese competitive programming circles. The technique long predates the name; Imos popularized it as a teaching tool for online judges. Worth knowing the term because it appears in CP-algorithms references.

8.4 Difference + Difference (Second-Order)

For problems like “add an arithmetic progression a, a+d, a+2d, ... to a range,” you can encode the linear increment with a second-order difference array: diff[l] += a, diff[l+1..r] += d (encoded with another difference operation), diff[r+1] -= a + (r - l) * d, diff[r+2] -= d. Reconstructing requires two prefix-sum sweeps. This is a niche but powerful trick for problems like LC 1674 (“Minimum Moves to Make Array Complementary”) and competitive-programming problems involving polynomial range updates.

9. Pitfalls

9.1 Off-by-One on the Closing Decrement

The most common bug. For an inclusive range [l, r], the decrement goes at r + 1; for a half-open range [l, r), it goes at r. Mismatching the convention to the problem statement leaves an extra “+v” hanging on the boundary cell, producing an answer that’s correct everywhere except at the right edge of each range. Always re-derive the boundary from the problem’s range convention.

9.2 Forgetting the Extra Slot

The difference array needs n + 1 slots if you’re using an inclusive end, because r + 1 may equal n. Allocating only n slots produces an IndexError on any update whose range ends at the last position. Allocate n + 1 and either ignore the extra slot during reconstruction or include it to verify the running sum returns to zero at the end (a free invariant check).

9.3 Trying to Mix Online Updates and Online Queries

Difference arrays are offline. If you need to answer a point or range query between range updates, you have two bad options: (a) reconstruct after every update at O(n) cost (defeating the purpose), or (b) maintain both the difference array and the live array (back to O(range) per update). For online interleaved workloads, switch to Segment Tree with Lazy Propagation or a Fenwick tree of differences.

9.4 Wrong Operation

Difference arrays exploit the inverse of the update operation. Addition has an inverse (subtraction); multiplication has an inverse (division, when defined); but max does not. There is no “anti-max” you can place at r + 1 to undo a range max operation, which is why range-max-update problems require segment trees. Knowing what won’t work prevents wasted effort.

9.5 2D Off-by-One on Four Corners

The 2D update touches four corners with alternating signs (+, −, −, +). Forgetting the doubly-decremented bottom-right corner (+v at [r2+1][c2+1]) leaves a triangular under-count in the bottom-right quadrant. The inclusion-exclusion derivation makes the sign pattern unambiguous; trying to memorize it directly is asking for trouble.

9.6 Confusing Difference Array with Prefix Sum

They are inverses, not the same thing. Prefix sums support O(1) range queries on a static array; difference arrays support O(1) range updates on a future-reconstructed array. Mixing them produces O(n) per operation in both directions. Drawing the integration/differentiation analogy explicitly helps keep the duality straight: prefix = ∫, difference = d/dx.

10. Diagram — Encoding a Range Update

flowchart LR
    subgraph original ["Conceptual: arr after update(2, 5, +3)"]
        A0["arr[0]<br/>0"]
        A1["arr[1]<br/>0"]
        A2["arr[2]<br/>+3"]
        A3["arr[3]<br/>+3"]
        A4["arr[4]<br/>+3"]
        A5["arr[5]<br/>+3"]
        A6["arr[6]<br/>0"]
    end
    subgraph diff ["Difference array: only boundaries are touched"]
        D0["diff[0]<br/>0"]
        D1["diff[1]<br/>0"]
        D2["diff[2]<br/>+3 ⬆"]:::edge
        D3["diff[3]<br/>0"]
        D4["diff[4]<br/>0"]
        D5["diff[5]<br/>0"]
        D6["diff[6]<br/>−3 ⬇"]:::edge
    end
    classDef edge fill:#ffd6a5,stroke:#000,color:#000

What this diagram shows. The top row depicts the conceptual effect of update(2, 5, +3) on the original array — every position from index 2 through 5 is incremented by +3, while positions 0, 1, and 6 are untouched. The bottom row shows the actual writes performed by the difference-array encoding: only two cells change. diff[2] += 3 marks the left edge of the range; diff[6] −= 3 marks the position just past the right edge (since the inclusive-end convention is in use here). When you sweep the difference array from left to right accumulating a running sum, the +3 at index 2 turns on the contribution and carries it forward through indices 2, 3, 4, 5; the −3 at index 6 cancels it out exactly at the boundary, returning the running sum to its pre-update value. The arrows mark the event positions — the only places where real writes happen — whereas the original-array view shows the integrated effect. Replacing length-of-range writes with two boundary writes is the entire algorithmic improvement.

11. Common Interview Problems

#	Problem	Why difference arrays
LC 370	Range Addition	Textbook 1D difference array
LC 1094	Car Pooling	1D difference array on stops; threshold check
LC 1109	Corporate Flight Bookings	1D difference array on flights
LC 1674	Minimum Moves to Make Array Complementary	Second-order difference array tracking pair-cost contributions
LC 798	Smallest Rotation with Highest Score	Difference array tracking score deltas across rotations
LC 2381	Shifting Letters II	Difference array on character shifts
LC 1893	Check If All the Integers in a Range Are Covered	1D difference array; check that running sum > 0 across [left, right]
LC 2406	Divide Intervals into Minimum Groups	Sweep-line / difference-on-events
LC 2536	Increment Submatrices by One	2D difference array, four-corner update
LC 850	Rectangle Area II	2D sweep line — close cousin to 2D difference arrays
LC 253	Meeting Rooms II	Sweep line on starts/ends — 1D difference in disguise

The Meeting Rooms II / Car Pooling family in particular shows up almost verbatim in real interviews; recognizing them as instances of “increment at start, decrement at end, find max running count” lets you write the solution in five minutes flat.

12. Open Questions

• Is there a clean characterization of which operations admit a difference-array encoding? Conjecture: the operation must form an Abelian group (commutative, associative, identity, inverse). Addition does; XOR does; multiplication on a field does; max does not (no inverse). Counterexamples to the conjecture would be interesting.
• In practice, how does the cache behavior of the difference-array sweep compare to a segment-tree’s pointer-chasing on modern CPUs? The difference-array sweep is purely sequential and ideal for prefetching; the segment tree has worse locality but supports interleaved operations.
• Is there a streaming version that supports unboundedly many range updates without storing the full difference array? Difficult — the boundary events can fall arbitrarily far apart. Some sketching schemes (e.g., Misra-Gries on event positions) might give approximate answers, but exact answers seem to require keeping all events.

13. See Also

• Prefix Sums — the inverse pattern; difference arrays + prefix sums together solve range-update + range-query offline
• Two Pointers — sibling array technique; sometimes substitutable, but solves a different cost-model problem
• Sliding Window — for contiguous-window aggregates rather than arbitrary-range updates
• Kadane’s Algorithm — different array technique for max-subarray; complementary in the array-pattern toolkit
• Segment Tree with Lazy Propagation — the online alternative when updates and queries interleave
• Binary Indexed Tree (Fenwick Tree) — supports range update + point query in O(log n); the online cousin of the difference-array idea
• Big-O Notation — for the O(k + n) vs. O(k × n) analysis
• SWE Interview Preparation MOC