Prefix Sums

A prefix-sum array stores, at each position, the running total of everything up to that point. Build it once in a single pass; after that the sum of any contiguous stretch is one subtraction, no matter how long the stretch. It trades a little upfront work for instant answers to many range-sum questions.

Build once, query forever

Define P[0] = 0 and P[i] = a[0] + … + a[i−1] (the sum of the first i elements). Then the sum of a[l..r] inclusive is simply P[r+1] − P[l]. For a = [3, 1, 4, 1, 5, 9, 2, 6] the prefix array is [0, 3, 4, 8, 9, 14, 23, 25, 31], so the sum of a[2..4] (values 4, 1, 5) is P[5] − P[2] = 14 − 4 = 10.

function buildPrefix(a) {
  const P = new Array(a.length + 1);
  P[0] = 0;                                // sum of nothing
  for (let i = 0; i < a.length; i++) P[i + 1] = P[i] + a[i];
  return P;
}

// sum of a[l..r] inclusive, in O(1):
const rangeSum = (P, l, r) => P[r + 1] - P[l];

The hashmap trick — subarray sum equals k

Prefix sums also count subarrays with a given sum k in one pass. A subarray a[l..r] sums to k exactly when P[r+1] − P[l] = k, i.e. P[l] = P[r+1] − k. So as you sweep, keep a hashmap of how many times each running sum has appeared; at each step add the count of sum − k already seen.

function subarraysEqualK(nums, k) {
  const seen = new Map([[0, 1]]); // one empty prefix of sum 0
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) || 0; // prefixes leaving a run summing to k
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

Run it on [1, 2, 3, -3, 3] with k = 3. The running sum hits 1, 3, 6, 3, 6; each step adds the count of sum − 3 seen so far, tallying 0 + 1 + 1 + 1 + 2 = 5 — the five subarrays [1,2], [3], [1,2,3,-3], [3], and [3,-3,3]. All in one O(n) pass instead of checking every subarray.