Prefix sums and difference arrays

Where this chapter picks up

If you met prefix sums in the arrays and strings chapter, you saw the idea once, in its smallest form: build a running total, answer a range sum with a subtraction. This chapter takes the idea over and follows it to the problems that do not look like range sums at all: counting subarrays that hit a target, the longest or shortest one, sums that divide evenly, XOR, products, range updates, and rectangles in a grid.

One convention is fixed from the start. Some presentations store, at each index, the sum up to and including that index, which forces a special case for ranges that begin at index 0. Here the table is one slot longer and begins with an explicit zero. The special case disappears, and every hash-map trick later in the chapter needs that leading zero anyway.

The idea: a range is the difference of two prefixes

Suppose you are given an array and then asked, many times, for the sum of nums[left..right]. The direct way adds the elements up for each query. A query can cover the whole array, so each one costs O(n), and q queries cost O(n·q). With 100,000 elements and 100,000 queries that is on the order of ten billion additions.

The waste is obvious once you notice that different queries add up the same elements again and again. So pay for the shared work once. Let P[i] be the sum of the first i elements, with P[0] = 0 for the empty prefix. Then P[right + 1] is everything from index 0 through right, and P[left] is everything from index 0 through left - 1. Subtract: the elements before left appear in both and cancel, and what remains is exactly nums[left..right].

// P[i] = sum of the first i elements; P[0] = 0 is the empty prefix. O(n) time, O(n) space.
function buildPrefix(nums) {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  return prefix;
}

// sum of nums[left..right], both inclusive. O(1).
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

const prefix = buildPrefix([2, -1, 3, 4, -2]); // [0, 2, 1, 4, 8, 6]
rangeSum(prefix, 1, 3); // 6

In an interview you will often be asked for this as a class, because the array is fixed and the queries arrive one at a time. The constructor does the O(n) work and each method call is a subtraction:

class NumArray {
  constructor(nums) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

Dry run: the table for [2, -1, 3, 4, -2]

Now rangeSum(prefix, 1, 3) reads prefix[4] - prefix[1], which is 8 − 2 = 6, and by hand -1 + 3 + 4 is also 6. A range that starts at index 0, such as rangeSum(prefix, 0, 4), needs no special case: it is prefix[5] - prefix[0] = 6 − 0.

Cost. Building is one pass: O(n) time and O(n) extra space. Each query is one subtraction: O(1). Together, n elements and q queries cost O(n + q), against O(n·q) for rescanning. The price is the extra array, and the assumption that the array does not change: the table describes the numbers as they were when you built it.

A cousin worth knowing is the pivot index problem: find the first index where the sum to its left equals the sum to its right. Here the prefix is never stored. The right side is total - left - nums[i], so a running left total and one initial pass for total are enough. The prefix idea does not always need the prefix array.

function pivotIndex(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  let left = 0; // sum of nums[0..i-1]
  for (let i = 0; i < nums.length; i++) {
    const right = total - left - nums[i]; // sum of nums[i+1..]
    if (left === right) return i;
    left += nums[i];
  }
  return -1;
}

Counting subarrays that hit a target: prefix sums plus a hash map

Now a different question. Given an array, how many contiguous subarrays sum to exactly k? The array may contain negative numbers.

The honest baseline checks every pair of endpoints: n(n + 1)/2 subarrays, so O(n²) even with a prefix table that makes each sum O(1). It is worth being able to write, because it is also your oracle for testing the fast version:

// O(n²) time, O(1) space. The baseline to state, and a checker for the fast version.
function subarraySumBrute(nums, k) {
  let count = 0;
  for (let start = 0; start < nums.length; start++) {
    let sum = 0;
    for (let end = start; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k) count++;
    }
  }
  return count;
}

If every number were non-negative you could use a sliding window: grow the right edge, and shrink the left edge while the sum is too big, because adding elements can only raise the sum. Negative numbers break that argument. A window that shrinks whenever its sum exceeds k, and counts a hit when its sum equals k, reports 3 on [1, -1, 1, 1] with k = 1, but the true answer is 5. Several different starts can work for the same end: for the end at index 2, both [1, -1, 1] and the single element [1] sum to 1, and the window holds only one start. And once negatives are allowed, "too big" no longer tells you which edge to move, because adding an element can lower the sum and removing one can raise it.

Go back to the two-prefix idea instead. A subarray that ends at index r and starts at index l has sum P[r + 1] − P[l]. It hits the target when

P[r + 1] − P[l] = k   ⇔   P[l] = P[r + 1] − k

So for each end r you do not need to try every start. You need to know how many earlier prefixes equal P[r + 1] − k. Keep a Map from each prefix value to how many times it has occurred, and look the answer up in O(1). Every earlier prefix that matches is one distinct start index, and so one distinct subarray.

// O(n) time (hash operations O(1) on average), O(n) space
function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]); // the empty prefix P[0] = 0 has occurred once
  let prefix = 0;
  let count = 0;

  for (const x of nums) {
    prefix += x;
    count += seen.get(prefix - k) ?? 0;          // look up BEFORE recording this prefix
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1); // now it is available to later ends
  }
  return count;
}

subarraySum([1, 1, 1], 2); // 2

Dry run: subarraySum([3, 4, -7, 1, 3, 3, 1, -4], 7)

Row 5 is the one to study. The prefix is 7 and we need earlier prefixes equal to 0. The prefix value 0 has occurred twice: as the empty prefix before index 0, and again after index 2 (because 3 + 4 − 7 = 0). Those are two different start positions, so two subarrays end here: [3, 4, −7, 1, 3, 3] and [1, 3, 3]. The four subarrays found overall are [3, 4], [3, 4, −7, 1, 3, 3], [1, 3, 3] and [3, 3, 1]. That is why the map stores counts, not just "seen or not".

Cost. One pass, one map lookup and one map write per element: O(n) time, assuming hash operations are O(1) on average, and O(n) space for the map. The answer itself is at most n(n + 1)/2, which is far inside the safe integer range for any array you can hold in memory.

Longest and shortest: which index you keep decides the answer

The same equation, P[l] = P[r + 1] − k, answers other questions once you choose what to store per prefix value. The lookup is identical; only the value kept in the map changes.

// longest subarray with sum k; 0 if none. O(n) time, O(n) space
function longestSubarraySum(nums, k) {
  const first = new Map([[0, -1]]); // the empty prefix ends before index 0, "at index -1"
  let prefix = 0;
  let best = 0;

  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i];
    if (first.has(prefix - k)) best = Math.max(best, i - first.get(prefix - k));
    if (!first.has(prefix)) first.set(prefix, i); // keep the EARLIEST index only
  }
  return best;
}

// shortest subarray with sum k; 0 if none. Same loop, other overwrite rule.
function shortestSubarraySum(nums, k) {
  const last = new Map([[0, -1]]);
  let prefix = 0;
  let best = Infinity;

  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i];
    if (last.has(prefix - k)) best = Math.min(best, i - last.get(prefix - k));
    last.set(prefix, i); // the LATEST index wins
  }
  return best === Infinity ? 0 : best;
}

longestSubarraySum([1, -1, 5, -2, 3], 3);  // 4
shortestSubarraySum([1, -1, 5, -2, 3], 3); // 1

The length of a subarray from start prefix l to end index i is i − (index of the start prefix). With the empty prefix stored at index −1, a subarray that begins at index 0 has length i − (−1) = i + 1, which is correct.

Dry run: longestSubarraySum([1, -1, 5, -2, 3], 3)

Look at row 1. The prefix 0 occurs again at index 1, but first already holds it, at index −1, from the empty prefix, so it is not overwritten. That is what lets row 3 find the start at −1 and report the length 4 (the subarray [1, −1, 5, −2]). If the line overwrote instead, row 3 would find the start at index 1 and report 2.

Remainders: sums that divide evenly

Now the target is not a number but a property: count the subarrays whose sum is divisible by k. A sum P[r + 1] − P[l] is divisible by k exactly when P[r + 1] and P[l] leave the same remainder when divided by k. Two numbers with equal remainders differ by a multiple of k, and two numbers that differ by a multiple of k have equal remainders. So the equality test is on remainders, and only k different remainders exist. A plain array of size k replaces the map:

// O(n) time, O(k) space. k is a positive integer.
function subarraysDivByK(nums, k) {
  const seen = new Array(k).fill(0); // seen[r] = earlier prefixes with remainder r
  seen[0] = 1;                        // the empty prefix has remainder 0
  let remainder = 0;
  let count = 0;

  for (const x of nums) {
    remainder = (((remainder + x) % k) + k) % k; // lands in 0..k-1, even for negative sums
    count += seen[remainder];
    seen[remainder]++;
  }
  return count;
}

subarraysDivByK([4, 5, 0, -2, -3, 1], 5); // 7

Dry run: subarraysDivByK([4, 5, 0, -2, -3, 1], 5)

The last row finds the seed: the prefix 5 has remainder 0, matching the empty prefix, so the whole array (sum 5) is one of the seven. Without seen[0] = 1 the answer would be 6.

Continuous Subarray Sum asks for a variation: does a subarray of length at least 2 exist whose sum is a multiple of k? Existence only, so no counts, but the length requirement means indices matter. Store the first index of each remainder, and accept an equal remainder only if the two prefixes are at least two elements apart.

// true if some subarray of length >= 2 has a sum that is a multiple of k (k >= 1). O(n) time, O(k) space.
function checkSubarraySum(nums, k) {
  const first = new Map([[0, -1]]); // remainder 0 "at index -1": the empty prefix
  let remainder = 0;

  for (let i = 0; i < nums.length; i++) {
    remainder = (((remainder + nums[i]) % k) + k) % k;
    if (!first.has(remainder)) first.set(remainder, i);
    else if (i - first.get(remainder) >= 2) return true; // at least two elements between the prefixes
  }
  return false;
}

checkSubarraySum([23, 2, 4, 6, 7], 6); // true: [2, 4] sums to 6
checkSubarraySum([1, 0], 2);            // false: the only multiple of 2 is the single element 0

Dry run: checkSubarraySum([23, 2, 4, 6, 7], 6)

The two prefixes with remainder 5 are the one after index 0 and the one after index 2. Everything between them, nums[1..2] = [2, 4], sums to 6. Keeping the first index matters: if a later occurrence overwrote it, a valid pair that is far apart could shrink to a length-1 pair and be rejected.

Turn the condition into a sum: the plus-one, minus-one trick

Many subarray conditions are not about sums at all, but become sums after a change of variables. The classic case is Contiguous Array: given a 0/1 array, find the longest subarray with equally many 0s and 1s. Counting both symbols is awkward. But replace every 0 with −1, and "equally many" is exactly "the sum is 0". Now you want the longest subarray with sum 0, which is the longest-subarray template with k = 0.

// longest subarray with equal numbers of 0s and 1s. O(n) time, O(n) space
function findMaxLength(nums) {
  const first = new Map([[0, -1]]);
  let balance = 0; // (#ones so far) - (#zeros so far)
  let best = 0;

  for (let i = 0; i < nums.length; i++) {
    balance += nums[i] === 1 ? 1 : -1;
    if (first.has(balance)) best = Math.max(best, i - first.get(balance));
    else first.set(balance, i);
  }
  return best;
}

findMaxLength([0, 1, 0, 0, 1, 1, 0]); // 6

With k = 0 the lookup key prefix − k is the prefix itself, so one map lookup replaces two, and the code above merges the "look up" and "record" steps into one if/else.

Dry run: findMaxLength([0, 1, 0, 0, 1, 1, 0])

At i = 5 the balance is back to 0, the value it had before any element. The subarray from index 0 to 5, [0, 1, 0, 0, 1, 1], has three 0s and three 1s. The answer is even, because equal counts of two kinds make the length twice the count.

The general move is to define a number per element that carries what you care about, then reuse a sum template. Counting subarrays with exactly k odd numbers: map each element to 1 if it is odd and 0 if even, and then you are counting subarrays that sum to k, which is subarraySum from earlier with a different running total:

function numberOfSubarrays(nums, k) {
  const seen = new Map([[0, 1]]);
  let odds = 0; // the running sum of the 0/1 version
  let count = 0;

  for (const x of nums) {
    if (x % 2 !== 0) odds++; // "!== 0", not "=== 1": -3 % 2 is -1 in JavaScript
    count += seen.get(odds - k) ?? 0;
    seen.set(odds, (seen.get(odds) ?? 0) + 1);
  }
  return count;
}

numberOfSubarrays([1, 1, 2, 1, 1], 3); // 2

Two relatives follow the same logic, and are in the practice list. In Longest Well-Performing Interval the condition is "strictly more tiring days than non-tiring days": score a tiring day +1 and any other day −1, and you want the longest subarray whose sum is positive, not equal to a number. When the current score s is positive, the whole prefix qualifies, because the empty prefix has score 0, which is lower. Otherwise the score started at 0 and moves by exactly 1 per day, so it must pass through s − 1 before it can reach anything lower. The earliest prefix below s is therefore the first occurrence of exactly s − 1, and a map of first indices still works. With larger steps the earliest lower prefix could be a value that you never stored a key for, so this shortcut is specific to ±1 scores.

Prefix XOR: when the operation undoes itself

Prefix sums work because addition has an inverse: subtracting a prefix removes exactly what it added. Bitwise XOR has an even nicer one: each value is its own inverse, since x ^ x = 0 and x ^ 0 = x. With P[i] = a[0] ^ a[1] ^ ... ^ a[i − 1], the XOR of a[l..r] is P[r + 1] ^ P[l]: the shared prefix appears twice and cancels itself.

// XOR of arr[left..right] for each query. O(n + q) time, O(n) space
function xorQueries(arr, queries) {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] ^ arr[i];
  return queries.map(([left, right]) => prefix[right + 1] ^ prefix[left]);
}

xorQueries([1, 3, 4, 8], [[0, 1], [1, 2], [0, 3], [3, 3]]); // [2, 7, 14, 8]

Everything from the sum sections carries over by replacing "minus" with "XOR". The number of subarrays whose XOR equals k: a subarray ends at r with start prefix P[l] when P[r + 1] ^ P[l] = k, that is, when P[l] = P[r + 1] ^ k. The loop is subarraySum with ^ in place of + and prefix ^ k in place of prefix − k (the practice list has it).

The harder application is Count Triplets That Can Form Two Arrays of Equal XOR. You want triples i < j ≤ k with XOR(arr[i..j−1]) = XOR(arr[j..k]). Two values are equal exactly when their XOR is 0, and the XOR of the two halves together is XOR(arr[i..k]). So the condition is XOR(arr[i..k]) = 0, that is, P[i] = P[k + 1]. And j has vanished from the condition: any of the j values in i + 1..k works, which is k − i of them.

// O(n²) time, O(n) space: for every pair of equal prefixes, add the number of valid j
function countTriplets(arr) {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] ^ arr[i];

  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let k = i + 1; k < arr.length; k++) {
      if (prefix[i] === prefix[k + 1]) count += k - i; // j can be i+1, ..., k
    }
  }
  return count;
}

countTriplets([2, 3, 1, 6, 7]); // 4

The pair loop can be replaced by a map. For each prefix value, keep how many earlier prefix positions had it and the sum of their positions. A new prefix at position b adds, for each earlier equal position a, the amount b − a − 1 (the same k − i, since k = b − 1 and i = a), and that total is howMany · (b − 1) − indexSum:

// O(n) time, O(n) space
function countTripletsFast(arr) {
  const seen = new Map(); // prefix value -> { howMany, indexSum } over earlier prefix positions
  let prefix = 0;
  let count = 0;

  const visit = (position) => {
    const entry = seen.get(prefix) ?? { howMany: 0, indexSum: 0 };
    count += entry.howMany * (position - 1) - entry.indexSum;
    entry.howMany++;
    entry.indexSum += position;
    seen.set(prefix, entry);
  };

  visit(0); // the empty prefix sits at position 0
  for (let i = 0; i < arr.length; i++) {
    prefix ^= arr[i];
    visit(i + 1);
  }
  return count;
}

Dry run: countTriplets([2, 3, 1, 6, 7])

Total: 2 + 2 = 4. For the first pair, j = 1 splits into [2] and [3, 1] (2 and 3 ^ 1 = 2), and j = 2 splits into [2, 3] and [1] (1 and 1). The brute-force triple loop gives the same 4.

Prefix products: when the operation has no safe inverse

A natural next try: P[i] is the product of the first i elements, and the product of a[l..r] is P[r + 1] / P[l]. Division is the inverse of multiplication, so the algebra works. The implementation has two problems. First, a single zero makes every later prefix 0, and you cannot divide by 0 to recover anything. Second, the products grow fast: 25! is about 1.55 × 10²⁵, far past the 2⁵³ − 1 limit up to which JavaScript numbers hold integers exactly, so the stored products, and the quotients made from them, can be inexact.

What does survive is the idea of an exclusive prefix and an exclusive suffix. In Product of Array Except Self you want, for each index, the product of everything except that element, and you may not divide. The answer at i is (the product of everything to the left of i) × (the product of everything to the right of i). Two sweeps give both factors, and the second can be folded into the output array, so the extra space beyond the output is O(1):

// O(n) time, O(1) extra space beyond the output
function productExceptSelf(nums) {
  const n = nums.length;
  const out = new Array(n).fill(1);

  let left = 1; // product of nums[0..i-1]
  for (let i = 0; i < n; i++) {
    out[i] = left;
    left *= nums[i];
  }

  let right = 1; // product of nums[i+1..n-1]
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= nums[i];
  }
  return out;
}

productExceptSelf([1, 2, 3, 4]); // [24, 12, 8, 6]
productExceptSelf([1, 0, 3]);    // [0, 3, 0]

Dry run: productExceptSelf([1, 2, 3, 4])

Zeros need no special handling: with [1, 0, 3] the left pass leaves [1, 1, 0], and the right pass turns it into [0, 3, 0], which is right, since every product that avoids the zero is taken over the other two elements only. One cosmetic quirk: 0 * -2 is -0 in JavaScript, so productExceptSelf([0, 5, -2]) contains a -0. === treats it as 0, but Object.is(-0, 0) is false, which matters only if a checker compares with it.

Difference arrays: the same idea run backwards

Everything so far read ranges. Now flip it: write to ranges. You are given an array of n zeros and many updates, each saying "add delta to every element from left to right", and you need the final array. Applying each update with a loop costs O(n) per update, so O(n·q) overall. Booking systems, car-pooling and "how many intervals cover this point" all have this shape.

The trick comes from asking what a prefix sum is the reverse of. Define the difference array D[i] = A[i] − A[i − 1], with A[−1] = 0: how much the array steps up or down at each index. Taking prefix sums of D gives back A, because each step is added to the running level. Now watch what "add d to A[l..r]" does to the steps. Inside the range every element rises by d together, so the step between neighbours is unchanged. Only two steps change: the step into the range at l rises by d, and the step out of it, at r + 1, falls by d.

So each update is two writes, O(1), and one final prefix-sum pass produces the array: O(n + q) in total.

// n elements starting at 0; each update is [left, right, delta], inclusive. O(n + q) time, O(n) space
function applyUpdates(n, updates) {
  const diff = new Array(n + 1).fill(0); // one spare slot so right + 1 === n is legal

  for (const [left, right, delta] of updates) {
    diff[left] += delta;       // the level rises here
    diff[right + 1] -= delta;  // and falls back right after the range
  }

  const result = new Array(n);
  let level = 0;
  for (let i = 0; i < n; i++) {
    level += diff[i]; // prefix sum of the steps
    result[i] = level;
  }
  return result;
}

applyUpdates(5, [[1, 3, 2], [2, 4, 3], [0, 2, -1]]); // [-1, 1, 4, 5, 3]

Dry run: applyUpdates(5, [[1, 3, 2], [2, 4, 3], [0, 2, -1]])

Index 3, for instance, is covered by the first and second updates (+2 and +3) but not the third (which ends at 2), and indeed its level is 5. The last entry of diff (−3 at index 5) is never read; its only job was to absorb the subtraction from the update that ended at the final index.

Car Pooling is the standard application. Trips are [passengers, from, to]; the load rises by that many at from and falls by the same amount at to, so the maximum load is the largest level of the running sum. Passengers leaving at a stop get out before new ones get in, and the code gets that rule for free: both changes land in the same slot and are added before the capacity is checked.

// O(trips + stops) time, O(stops) space
function carPooling(trips, capacity) {
  let lastStop = 0;
  for (const trip of trips) lastStop = Math.max(lastStop, trip[2]);

  const change = new Array(lastStop + 1).fill(0);
  for (const [passengers, from, to] of trips) {
    change[from] += passengers;
    change[to] -= passengers; // drop-off at "to": the seat is free again AT stop "to"
  }

  let onBoard = 0;
  for (const delta of change) {
    onBoard += delta;
    if (onBoard > capacity) return false;
  }
  return true;
}

carPooling([[2, 1, 5], [3, 3, 7]], 4); // false: stops 3 and 4 hold 5 passengers
carPooling([[2, 1, 5], [3, 5, 7]], 3); // true: the 2 get out at 5 before the 3 get in

The same shape appears whenever you count overlapping intervals at a point: how many meetings are in progress, the maximum number of simultaneous bookings, or the flights-booked-per-day problem, where the only extra step is shifting a 1-based range to a 0-based index. When the coordinates are huge or sparse, a difference array of that size is wasteful: record the changes in a Map (or sort the endpoints) and sweep the keys in order, which is the sweep-line technique in the intervals chapter.

Two dimensions: rectangle sums by inclusion and exclusion

A grid with many rectangle-sum queries has the same shape as the 1D problem, with a worse brute force: a query over a big rectangle touches up to rows × cols cells. The 1D idea extends if you define the prefix as a rectangle anchored at the top-left corner. Let P[r][c] be the sum of all cells with row index below r and column index below c (the first r rows and the first c columns). As in 1D, row 0 and column 0 of the table are zeros, so P has (rows + 1) × (cols + 1) entries.

Building it. The rectangle ending at cell (r, c) is the cell itself, plus the rectangle that ends one row above, plus the rectangle that ends one column to the left. But the two neighbouring rectangles both contain everything above-left of the cell, so that region has been counted twice, and we subtract it once:

P[r + 1][c + 1] = a[r][c] + P[r][c + 1] + P[r + 1][c] − P[r][c]

Querying. Take the rectangle with corners (r1, c1) and (r2, c2), both inclusive. Start from the big prefix rectangle that reaches (r2, c2), remove the strip above the query and the strip to its left, and notice that the corner where those two strips overlap was removed twice, so add it back once. This is inclusion and exclusion.

// build: O(rows·cols). Each query: O(1). Space: O((rows+1)·(cols+1))
class NumMatrix {
  constructor(matrix) {
    const rows = matrix.length;
    const cols = rows === 0 ? 0 : matrix[0].length;

    // Array.from with a callback: every row is its OWN array
    this.prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));

    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        this.prefix[r + 1][c + 1] =
          matrix[r][c] + this.prefix[r][c + 1] + this.prefix[r + 1][c] - this.prefix[r][c];
      }
    }
  }

  sumRegion(r1, c1, r2, c2) {
    const p = this.prefix;
    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
  }
}

Dry run: matrix [[3, 0, 1], [5, 6, 3], [1, 2, 0]]

Check one cell with the build rule: prefix[2][2] is matrix[1][1] + prefix[1][2] + prefix[2][1] − prefix[1][1] = 6 + 3 + 8 − 3 = 14, and the top-left 2×2 block 3 + 0 + 5 + 6 is 14. Now the query sumRegion(1, 1, 2, 2), the bottom-right 2×2 block: prefix[3][3] − prefix[1][3] − prefix[3][1] + prefix[1][1] = 21 − 4 − 9 + 3 = 11, and by hand 6 + 3 + 2 + 0 is 11.

Matrix Block Sum builds directly on the table. For each cell, the wanted block runs from i − k to i + k in each direction, clamped to the grid. Clamp the four corners with Math.max(0, ...) and Math.min(last, ...) and use the same four-term query: O(rows·cols) total, however large k is.

function matrixBlockSum(mat, k) {
  const rows = mat.length;
  const cols = mat[0].length;
  const grid = new NumMatrix(mat);

  return mat.map((row, i) =>
    row.map((_, j) =>
      grid.sumRegion(
        Math.max(0, i - k),
        Math.max(0, j - k),
        Math.min(rows - 1, i + k),
        Math.min(cols - 1, j + k)
      )
    )
  );
}

The harder relative, Number of Submatrices That Sum to Target, joins the 2D table to the hash-map idea from earlier. Fix a top row and a bottom row. Every rectangle between them is a run of consecutive columns, and its sum is the sum of the column totals over that run. For a fixed pair of rows the column totals form a 1D array, and the question "how many runs sum to the target" is subarraySum. Loop the bottom row downward, adding one row at a time into the column totals:

// O(rows² · cols) time, O(cols) extra space; reuses subarraySum from earlier
function numSubmatrixSumTarget(matrix, target) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let count = 0;

  for (let top = 0; top < rows; top++) {
    const columnTotals = new Array(cols).fill(0);
    for (let bottom = top; bottom < rows; bottom++) {
      for (let c = 0; c < cols; c++) columnTotals[c] += matrix[bottom][c];
      count += subarraySum(columnTotals, target); // 1D problem for this pair of rows
    }
  }
  return count;
}

numSubmatrixSumTarget([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0); // 4

There are rows(rows + 1)/2 pairs of rows and each costs O(cols), so the total is O(rows² · cols). The row pairs are the squared factor, so when the grid is not square it is cheaper to take the smaller dimension as "rows" (transpose first if needed).

The 2D difference array mirrors the 1D one with four corners. To add d to the rectangle (r1, c1)–(r2, c2), write +d at its top-left, −d just right of its top-right and just below its bottom-left, and +d diagonally past its bottom-right. A 2D prefix sum over the table then yields the final grid:

// diff has (rows + 1) rows and (cols + 1) columns
function addRectangle(diff, r1, c1, r2, c2, delta) {
  diff[r1][c1] += delta;
  diff[r1][c2 + 1] -= delta;
  diff[r2 + 1][c1] -= delta;
  diff[r2 + 1][c2 + 1] += delta;
}

function rebuild(diff, rows, cols) {
  const out = Array.from({ length: rows }, () => new Array(cols).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      out[r][c] =
        diff[r][c] + (r ? out[r - 1][c] : 0) + (c ? out[r][c - 1] : 0) - (r && c ? out[r - 1][c - 1] : 0);
    }
  }
  return out;
}

The rebuild is the same inclusion-exclusion as the 2D prefix build, with the guards standing in for the leading row and column of zeros.

Choosing between the tools

Prefix sums are one of several tools for range questions, and the decision is mostly about what changes and what is being asked.

The sliding-window row is worth saying aloud in an interview. Prefix sums with a map are the more general tool (they handle negatives), and a window is the lighter one (no map, constant space) when its monotonicity argument applies. See the hashing chapter for the map half of the pairing.

Recognizing it in an unseen problem

• The statement says subarray, contiguous, range, interval or rectangle, and asks for a sum, a count of something, or a balance between two kinds of element
• The brute force is "for every pair of endpoints, compute the thing", O(n²) or O(n³): a prefix table makes each evaluation O(1), and a map can remove the inner loop entirely
• The input contains negative numbers and the problem is about an exact sum. This is the signal to prefer prefix sums plus a map over a sliding window
• "Equal numbers of A and B" becomes "sum is 0" after mapping A to +1 and B to −1; "exactly k things with a property" becomes "sum is k" after mapping each element to 0 or 1
• "Divisible by k", "a multiple of k" or a remainder condition means equal prefix remainders, and an array of size k or a map keyed by remainder
• XOR over a range means prefix XOR. If a triplet or pair condition says two XORs are equal, ask whether their combination is 0
• Many "add to a range" operations followed by a single read of the array (bookings, overlaps, capacity) means a difference array. "How many intervals cover this point" is the same thing
• A grid with many rectangle queries means a 2D prefix table. A question about every rectangle in a grid often means fixing two rows and solving a 1D problem
• If the array changes between queries, a plain prefix table is stale: move to a Fenwick or segment tree. If the question is about min or max, prefix tricks do not apply

The mistakes that lose offers

• Forgetting the empty prefix. Seeding the map with {0: 1} (or {0: -1} for indices) is what lets subarrays that start at index 0 count. It is the most common single bug in this chapter
• Recording before looking up. This only shows up when k = 0, so test k = 0 deliberately
• Overwriting the first index in a "longest" question, or not overwriting it in a "shortest" one
• Using a sliding window with negative numbers. A window that shrinks when the sum is too big cannot tell which edge to move
• Negative remainders. -7 % 5 is -2 in JavaScript. Normalise with ((x % k) + k) % k; and x % 0 is NaN
• Tests for odd that use === 1. -3 % 2 is -1
• 32-bit bitwise operators. ^ and & truncate to 32 bits; use BigInt for larger values
• Off-by-one at the end of a difference array. Allocate n + 1 so right + 1 is a valid index
• Shared rows in a 2D table built with fill(new Array(...)), and a table without its leading row and column of zeros
• A stale table. The prefix table describes the array as it was when built; if elements change, it is wrong from the first changed index onward