Prefix Sums & Difference Arrays

The idea

Precompute P[i] = a[0] + a[1] + … + a[i−1] (with P[0] = 0). Then the sum of any range is a subtraction:

sum(a[l..r]) = P[r + 1] − P[l]

O(n) preprocessing, O(1) per query. The real power, though, is that it turns “subarray sum” questions into “pair of prefix values” questions, which hash maps and sorting can answer.

Template: 1D prefix sums

def build_prefix(a):
    P = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        P[i + 1] = P[i] + x
    return P

# sum of a[l..r] inclusive
def range_sum(P, l, r):
    return P[r + 1] - P[l]

# Python shortcut
from itertools import accumulate
P = [0, *accumulate(a)]

vector<long long> P(n + 1, 0);
for (int i = 0; i < n; i++) P[i + 1] = P[i] + a[i];
// sum of a[l..r] inclusive
auto rangeSum = [&](int l, int r) { return P[r + 1] - P[l]; };

Pattern: prefix sum + hash map

A subarray (i, j] sums to k exactly when P[j] − P[i] = k, i.e. P[i] = P[j] − k. Scan j left to right, keeping a hash map of prefix values seen so far.

Count subarrays with sum k

def subarray_sum(nums, k):
    seen = {0: 1}                # the empty prefix
    P = count = 0
    for x in nums:
        P += x
        count += seen.get(P - k, 0)
        seen[P] = seen.get(P, 0) + 1
    return count

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> seen{{0, 1}};
    long long P = 0; int count = 0;
    for (int x : nums) {
        P += x;
        auto it = seen.find(P - k);
        if (it != seen.end()) count += it->second;
        seen[P]++;
    }
    return count;
}

Longest subarray with sum k

Store the first index where each prefix value appears (to maximize length).

def max_len_sum_k(nums, k):
    first = {0: -1}
    P = best = 0
    for i, x in enumerate(nums):
        P += x
        if P - k in first:
            best = max(best, i - first[P - k])
        first.setdefault(P, i)        # keep the earliest
    return best

Reductions to this template:

Subarrays divisible by k

def subarrays_div_by_k(nums, k):
    count = [0] * k
    count[0] = 1
    P = res = 0
    for x in nums:
        P = (P + x) % k          # Python % is always non-negative
        res += count[P]
        count[P] += 1
    return res

2D prefix sums

S[i][j] = sum of the rectangle from (0,0) to (i−1, j−1). Inclusion–exclusion builds and queries it.

def build_2d(M):
    R, C = len(M), len(M[0])
    S = [[0] * (C + 1) for _ in range(R + 1)]
    for i in range(R):
        for j in range(C):
            S[i + 1][j + 1] = M[i][j] + S[i][j + 1] + S[i + 1][j] - S[i][j]
    return S

def rect_sum(S, r1, c1, r2, c2):      # inclusive corners
    return S[r2 + 1][c2 + 1] - S[r1][c2 + 1] - S[r2 + 1][c1] + S[r1][c1]

vector<vector<long long>> S(R + 1, vector<long long>(C + 1, 0));
for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++)
        S[i + 1][j + 1] = M[i][j] + S[i][j + 1] + S[i + 1][j] - S[i][j];
auto rect = [&](int r1, int c1, int r2, int c2) {
    return S[r2 + 1][c2 + 1] - S[r1][c2 + 1] - S[r2 + 1][c1] + S[r1][c1];
};

Submatrix sum equals target: fix a pair of rows (O(R²)), collapse columns into a 1D array of column sums, and run the 1D hash-map count → O(R²·C).

Difference arrays: range updates in O(1)

The inverse of prefix sums. To add x to every element in [l, r]:

diff[l] += x
diff[r + 1] -= x

After all updates, a prefix sum over diff reconstructs the final array. k updates on n elements: O(n + k) instead of O(n·k).

def apply_updates(n, updates):          # updates: (l, r, x), inclusive
    diff = [0] * (n + 1)
    for l, r, x in updates:
        diff[l] += x
        diff[r + 1] -= x
    out, running = [], 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out

vector<long long> applyUpdates(int n, const vector<array<int, 3>>& updates) {
    vector<long long> diff(n + 1, 0), out(n);
    for (auto& [l, r, x] : updates) { diff[l] += x; diff[r + 1] -= x; }
    long long running = 0;
    for (int i = 0; i < n; i++) { running += diff[i]; out[i] = running; }
    return out;
}

This is the sweep line idea in disguise: Car Pooling, Meeting Rooms II (max overlap), My Calendar, Corporate Flight Bookings. When coordinates are huge, use a sorted map of events instead of an array.

2D difference arrays work the same way with four corner updates: d[r1][c1] += x; d[r1][c2+1] -= x; d[r2+1][c1] -= x; d[r2+1][c2+1] += x, then a 2D prefix sum.

Beyond sums

Anything invertible works like a prefix sum:

• Prefix XOR: xor(l..r) = PX[r+1] ^ PX[l].
• Prefix counts: count of 'a' in s[l..r] with one prefix array per letter.
• Prefix products (no zeros, or handle zeros separately).

Things that are not invertible — min, max, gcd — need a sparse table or segment tree for range queries.

When values can be negative and you want “sum ≥ k”

Sliding window fails, and a hash map only answers “= k”. For shortest subarray with sum ≥ k, keep a monotonic increasing deque of prefix indices:

from collections import deque

def shortest_subarray(nums, k):
    P = [0]
    for x in nums:
        P.append(P[-1] + x)
    dq, best = deque(), float("inf")
    for j in range(len(P)):
        while dq and P[j] - P[dq[0]] >= k:
            best = min(best, j - dq.popleft())    # front can't do better later
        while dq and P[dq[-1]] >= P[j]:
            dq.pop()                               # a later, smaller prefix dominates
        dq.append(j)
    return best if best != float("inf") else -1

Common mistakes

• Off-by-one between P[r] and P[r+1]. With the leading zero: sum(l..r) = P[r+1] − P[l].
• Forgetting to seed the hash map with prefix 0 (misses subarrays starting at index 0).
• Negative modulo in C++/Java: (-3) % 5 == -3. Normalize with ((x % k) + k) % k.
• Overflow: prefix sums of 10⁵ values up to 10⁹ need 64-bit integers.
• Updating the map before querying it when a subarray must be non-empty.