Prefix Sum

"Precompute running sums for O(1) range queries and subarray counting."

Deep Dive Tutorial

Prefix sum is the most underused O(1) trick in competitive programming. Build it once in O(n), then answer any "sum of nums[i..j]" in O(1). The difference array is the inverse: instead of querying, it does range updates in O(1). Together they handle range sum queries, 2D queries, and interval coverage problems that nested loops would solve in O(n²).

Prefix Sum — Range Query in O(1)

1D prefix sum template

// Build: O(n)
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];

// Query sum of nums[l..r] (0-indexed, inclusive): O(1)
const rangeSum = (l, r) => prefix[r+1] - prefix[l];

// Common usage: check if subarray sum === target
// sum(l..r) = target → prefix[r+1] - prefix[l] = target → prefix[l] = prefix[r+1] - target
// So: track seen prefix sums in a hashmap!
const countSubarraysWithSum = (nums, target) => {
    const prefix = new Map([[0, 1]]); // prefix sum 0 seen once (before start)
    let count = 0, sum = 0;
    for (const n of nums) {
        sum += n;
        count += (prefix.get(sum - target) ?? 0);
        prefix.set(sum, (prefix.get(sum) ?? 0) + 1);
    }
    return count;
};

Prefix Sum + Hashmap (the two-sum pattern)

key

Key insight for "count subarrays with sum = k":
sum(l..r) = k means prefix[r] - prefix[l-1] = k, i.e., prefix[l-1] = prefix[r] - k.

For each position r, look up how many past prefix sums equal prefix[r] - k.
Same pattern as two-sum: use a hashmap to count occurrences.

Why this beats sliding window: works with NEGATIVE numbers (sliding window requires all-positive for monotonicity).

Difference Array — Range Updates in O(1)

Difference array — O(1) updates, O(n) to reconstruct

// Add delta to all nums[l..r] in O(1)
const diff = new Array(n + 1).fill(0);
const rangeAdd = (l, r, delta) => {
    diff[l] += delta;
    diff[r + 1] -= delta;  // stop adding after r
};

// Reconstruct original array after all updates: O(n)
const result = new Array(n).fill(0);
let running = 0;
for (let i = 0; i < n; i++) {
    running += diff[i];
    result[i] = running;
}

// Use case: "apply k range updates, then query each element"
// Without diff array: O(k·n). With diff array: O(k + n).

2D Prefix Sum

2D prefix sum — O(1) rectangle sum query

// Build: prefix[i][j] = sum of rectangle (0,0) to (i-1,j-1)
const buildPrefix2D = (matrix) => {
    const m = matrix.length, n = matrix[0].length;
    const p = Array.from({length:m+1}, () => new Array(n+1).fill(0));
    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            p[i][j] = matrix[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
    return p;
};

// Query sum of rectangle (r1,c1) to (r2,c2) — 0-indexed: O(1)
const query2D = (p, r1, c1, r2, c2) =>
    p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];