Prefix Sums, Difference Arrays & Coordinate Compression

1. Problem and Motivation

A recurring interview and systems question looks like this: given a static array, answer many queries of the form "what is the sum of elements from index $l$ to $r$?" Re-summing the range on every query costs $O(n)$ per query and $O(nq)$ for $q$ queries. A prefix sum array fixes this: pay $O(n)$ once to build it, then answer every subsequent range-sum query in $O(1)$.

The mirror-image problem inverts the same idea. Instead of many range reads, a system receives many range writes — "add $v$ to every element from index $l$ to $r$" — and only needs the final array once all updates are applied. A difference array makes each update $O(1)$ and reconstructs the final array in a single $O(n)$ pass at the end.

A third, related technique solves a different problem entirely. When values are sparse or enormous (say, up to $10^9$) but only their relative order matters, coordinate compression remaps them onto a dense range $[0, n)$ so they can index a small array — or feed a Fenwick Tree, as you will see later in this lesson. All three techniques share one habit of mind: trade a small amount of preprocessing or postprocessing for a running aggregate, instead of recomputing a quantity from scratch every time it is needed.

2. Prerequisites

This lesson assumes comfort with arrays, zero-based indexing, and simple loop invariants — the material covered in Part 3: Arrays & Array ADT Operations, particularly static array indexing, insertion and deletion cost, and linear scanning. You should also be comfortable reading and writing to a hash map (used in the Subarray Sum Equals K pattern) and know how sorting and binary search work (used for coordinate compression). No prior exposure to Fenwick Trees or segment trees is required. This lesson deliberately stops at the point where those structures take over, and points you to them at the right moment.

3. A Concrete Example

The trace exposes the key invariant: prefix[i] always equals the sum of the first $i$ elements of arr, and an inclusive range sum is just a subtraction of two such totals.

4. Core Insight

1. Allocate prefix with length $n+1$ and set prefix[0] = 0.
2. For $i$ from 1 to $n$: prefix[i] = prefix[i-1] + arr[i-1].
3. For any inclusive query range $[l, r]$ with $0 \le l \le r \lt n$: the answer is prefix[r+1] - prefix[l].
4. Step 1-2 run once in $O(n)$; step 3 runs in $O(1)$ per query, however many queries arrive afterward.

5. Correctness

Prove the invariant "prefix[i] equals the sum of arr[0..i-1]" by induction on $i$:

1. Base case: prefix[0] = 0, the sum of an empty prefix, which is correct by definition.
2. Inductive step: assume prefix[i-1] is the sum of arr[0..i-2]. Then prefix[i] = prefix[i-1] + arr[i-1] is that sum plus the next element, which is exactly the sum of arr[0..i-1].
3. Range formula: since prefix[r+1] is the sum of arr[0..r] and prefix[l] is the sum of arr[0..l-1], their difference removes the shared prefix arr[0..l-1] and leaves exactly arr[l..r].

This is why the array must stay static between the build step and any query: any mutation to arr after prefix is built invalidates every following entry, because each entry depends on all elements before it.

6. Complexity Analysis

The break-even point is simple: if you expect more than one range query on data that will not change, the $O(n)$ preprocessing pays for itself immediately. If the array must also support point or range updates interleaved with queries, a plain prefix sum array stops being sufficient — every update after the point of change would force an $O(n)$ rebuild.

7. Three-Language Implementation

Each panel builds a 1D prefix sum array once and then answers an inclusive range-sum query in constant time, using the same sample array and query used in the worked example above.

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i in range(1, len(prefix)):
        prefix[i] = prefix[i - 1] + arr[i - 1]
    return prefix

def range_sum(prefix, l, r):
    """Inclusive sum of arr[l..r], 0-indexed."""
    return prefix[r + 1] - prefix[l]

sample = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(sample)
print("Range sum (2..5):", range_sum(prefix, 2, 5))  # 19

#include <iostream>
#include <vector>

std::vector<long long> buildPrefix(const std::vector<int>& arr) {
    std::vector<long long> prefix(arr.size() + 1, 0);
    for (std::size_t i = 1; i < prefix.size(); ++i) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
    return prefix;
}

long long rangeSum(const std::vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

int main() {
    std::vector<int> sample{3, 1, 4, 1, 5, 9, 2, 6};
    auto prefix = buildPrefix(sample);
    std::cout << "Range sum (2..5): " << rangeSum(prefix, 2, 5) << '\n'; // 19
}

import java.util.List;

public class PrefixSum {
    static long[] buildPrefix(List<Integer> arr) {
        long[] prefix = new long[arr.size() + 1];
        for (int i = 1; i < prefix.length; i++) {
            prefix[i] = prefix[i - 1] + arr.get(i - 1);
        }
        return prefix;
    }

    static long rangeSum(long[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l];
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(3, 1, 4, 1, 5, 9, 2, 6);
        long[] prefix = buildPrefix(sample);
        System.out.println("Range sum (2..5): " + rangeSum(prefix, 2, 5)); // 19
    }
}

8. Deep Dives

1D Prefix Sums

The technique above generalizes without change to negative numbers, floating-point values, or any associative, invertible operation — addition is invertible because subtraction undoes it. The name varies by context ("running sum," "cumulative sum," "integral"), but the invariant is always the same one proven in Section 5: prefix[i] is the total of everything strictly before index $i$. Keep this generalization in mind before reaching for a heavier tool: many problems that look like they need a segment tree are really a static 1D prefix sum in disguise.

2D Prefix Sums

The same idea extends to a matrix. Define prefix[i][j] as the sum of the submatrix from (0,0) to (i-1,j-1). Building it needs an inclusion-exclusion correction, because the sum above and the sum to the left both double-count the overlapping corner:

$$prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]$$

Querying the sum of the rectangle from (r1,c1) to (r2,c2) inclusive applies the same correction in reverse, subtracting the two rectangles that lie outside the target and adding back the doubly-subtracted corner:

$$prefix[r2{+}1][c2{+}1] - prefix[r1][c2{+}1] - prefix[r2{+}1][c1] + prefix[r1][c1]$$

def build_prefix_2d(mat):
    rows, cols = len(mat), len(mat[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix[i][j] = (prefix[i - 1][j] + prefix[i][j - 1]
                             - prefix[i - 1][j - 1] + mat[i - 1][j - 1])
    return prefix

def submatrix_sum(prefix, r1, c1, r2, c2):
    """Inclusive sum of mat[r1..r2][c1..c2]."""
    return (prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
            - prefix[r2 + 1][c1] + prefix[r1][c1])

This is the same trick behind "summed-area tables" in computer vision, used to compute the average brightness of any rectangular window in $O(1)$ regardless of its size.

Prefix XOR and Prefix Frequency

Subtraction is not the only invertible operation. XOR is its own inverse ($x \oplus x = 0$), so a prefix XOR array answers "what is the XOR of arr[l..r]?" with prefixXor[r+1] ^ prefixXor[l], exactly like the sum case.

A more powerful pattern combines a running prefix sum with a hash map of how many times each prefix sum has occurred — this solves Subarray Sum Equals K (LeetCode 560) without ever materializing the full prefix array. If prefix_sum is the running total through index $i$, then a subarray ending at $i$ sums to $k$ exactly when an earlier prefix sum equalled prefix_sum - k. Counting how many earlier prefixes match that value, for every $i$, counts every qualifying subarray in one pass:

def subarray_sum(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}  # an empty prefix (sum 0) occurs once, before any element
    for num in nums:
        prefix_sum += num
        count += seen.get(prefix_sum - k, 0)
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1
    return count

print(subarray_sum([1, 1, 1], 2))  # 2

The hash map turns "find a matching earlier prefix" from an $O(n)$ scan into an $O(1)$ expected-time lookup, so the whole algorithm runs in $O(n)$ time and $O(n)$ space.

Difference Arrays

A difference array inverts the prefix sum idea for writes instead of reads. To add $v$ to every element in arr[l..r], record only the two boundary changes: diff[l] += v and diff[r+1] -= v. After every update has been recorded this way, a single prefix sum pass over diff reconstructs the fully updated array:

def apply_range_updates(n, updates):
    """updates: list of (l, r, v) meaning add v to arr[l..r] inclusive."""
    diff = [0] * (n + 1)
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v

    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running
    return result

print(apply_range_updates(5, [(1, 3, 2), (0, 4, 1)]))  # [1, 3, 3, 3, 1]

Each update costs $O(1)$ regardless of how wide the range is, and the final reconstruction costs $O(n)$ once, no matter how many updates were recorded. This is strictly better than applying each update directly to arr, which costs $O(r-l+1)$ per update.

The same trick lifts to two dimensions, often called the Imos method: to add $v$ to a rectangle, mark its four corners in a 2D difference grid — +v at the top-left, -v at the positions one past the right edge and one past the bottom edge, and +v at the position diagonally one past both — then reconstruct the final grid with the same 2D prefix sum pass described earlier in this section. The bookkeeping is more fiddly than the 1D case, but the underlying idea — cancel updates at boundaries, then integrate once — is unchanged.

Coordinate Compression

Coordinate compression solves a different kind of problem: the values themselves are fine, but there are either too many of them or they are too spread out to use directly as array indices. Consider Count of Smaller Numbers After Self (LeetCode 315): for each element, count how many elements to its right are strictly smaller. Values can range across $\pm 10^4$ or wider in other variants, so allocating an array indexed directly by value would be wasteful or impossible — but the algorithm only ever needs to know each value's rank among the distinct values present.

Compression maps every value to a dense index in $[0, m)$, where $m$ is the number of distinct values: sort the distinct values once, then look up each value's position in that sorted list, either with a hash map (as below) or with binary search (bisect_left) when you cannot afford to materialize the map.

nums = [5, 2, 6, 1]
sorted_unique = sorted(set(nums))                       # [1, 2, 5, 6]
rank = {value: i for i, value in enumerate(sorted_unique)}
compressed = [rank[value] for value in nums]

print(compressed)  # [2, 1, 3, 0] -- dense ranks in [0, len(sorted_unique))

Sorting costs $O(m \log m)$ and each lookup is $O(1)$ with the hash map or $O(\log m)$ with binary search, so compressing $n$ values costs $O(n \log n)$ overall — the same order as the sort itself.

9. Applications and Alternatives

Choose the alternative that matches how the data changes. A static array with occasional range queries wants a plain prefix sum array, $O(n)$ build and $O(1)$ query. An array that also needs point updates interleaved with prefix queries wants a Fenwick Tree, $O(\log n)$ for both operations. An array that needs arbitrary range updates and range queries, or non-invertible aggregates like range minimum, wants a segment tree, at the cost of a more involved implementation. A difference array is the right tool only when all the updates arrive before you need to read the array — it does not support interleaved reads.

10. Exercises and Mastery

Easy

1. Implement Range Sum Query - Immutable (LeetCode 303): build a NumArray class that precomputes a prefix sum array in its constructor and answers sumRange(l, r) in $O(1)$.

Medium

1. Solve Subarray Sum Equals K (LeetCode 560) using the prefix-sum-plus-hash-map pattern from Section 8, and verify its time complexity against a brute-force $O(n^2)$ double loop.

Hard

1. Solve Range Addition (LeetCode 370): given an array length $n$ and a list of updates [l, r, v] meaning "add $v$ to every index from $l$ to $r$," build a difference array, apply every update in $O(1)$ each, and reconstruct the final array with one $O(n)$ prefix sum pass.

Review rhythm: tomorrow, rebuild the prefix sum and difference array formulas from memory without looking back. Next week, implement Range Addition and Subarray Sum Equals K without notes. Several weeks later, recognize the same "cancel at boundaries, integrate once" idea inside a new problem, and explain to someone else exactly when a plain prefix sum array stops being sufficient and a Fenwick Tree or segment tree takes over.

11. Summary Cheat Sheet

• Prefix sum: prefix[i] = prefix[i-1] + arr[i-1]; range sum is prefix[r+1] - prefix[l]; $O(n)$ build, $O(1)$ query.
• 2D prefix sum uses inclusion-exclusion on four corners to sum any submatrix in $O(1)$ after $O(rows \times cols)$ preprocessing.
• Prefix XOR mirrors prefix sum for XOR ranges; a hash map of prefix-sum frequencies solves Subarray Sum Equals K in $O(n)$.
• Difference array: diff[l] += v; diff[r+1] -= v makes each range update $O(1)$; one prefix sum pass reconstructs the array in $O(n)$.
• The Imos method is the 2D analogue of a difference array: mark four corners per rectangle update, then reconstruct with a 2D prefix sum.
• Coordinate compression maps a sparse or huge value range to dense ranks $[0, m)$ via sort plus hash map or binary search, in $O(n \log n)$.
• All three techniques are static preprocessing tricks; once updates and queries interleave, upgrade to a Fenwick Tree or segment tree.