Prefix Sums

The problem

A fitness app stores daily step counts and lets users ask, again and again, "How many steps from day 3 to day 10?" Adding the range each time is O(n) per question. With thousands of questions that adds up.

How to spot it

• Many range-sum questions on the same array ("sum from i to j")
• "Number of subarrays whose sum equals k" (especially with negative numbers, where a window fails)
• Products or counts "before and after" each index (product of array except self)
• 2D versions: sums over rectangles in a grid

The idea

Build a running-total array once: prefix[i] = sum of the first i numbers, with prefix[0] = 0. Then the sum of positions i to j is just:

sum(i..j) = prefix[j + 1] - prefix[i]

It's like a car's odometer: distance for one trip = reading at the end − reading at the start.

Counting subarrays that sum to k: walking left to right with a running total total, a subarray ending here sums to k exactly when some earlier running total was total - k. Keep a map of how many times each running total has appeared (that's the hash-map pattern again).

The template

prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
range_sum = prefix[j + 1] - prefix[i]

# count subarrays summing to k
seen = {0: 1}          # running total -> how many times
total = count = 0
for x in nums:
    total += x
    count += seen.get(total - k, 0)
    seen[total] = seen.get(total, 0) + 1

const prefix = [0];
for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);
const rangeSum = prefix[j + 1] - prefix[i];

// count subarrays summing to k
const seen = new Map([[0, 1]]);   // running total -> how many times
let total = 0, count = 0;
for (const x of nums) {
  total += x;
  count += seen.get(total - k) ?? 0;
  seen.set(total, (seen.get(total) ?? 0) + 1);
}

Worked example

Range sums on step counts, counting subarrays with sum k (with a negative number in the input), and "product of array except self" using a running product from each side.

def build_prefix(nums):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    return prefix


def count_subarrays_with_sum(nums, k):
    seen = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count


def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):              # product of everything to the left
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):  # times everything to the right
        out[i] *= right
        right *= nums[i]
    return out


steps = [4000, 8000, 6500, 12000, 3000, 9000]
prefix = build_prefix(steps)
print("days 1-3:", prefix[4] - prefix[1])
print("days 0-5:", prefix[6] - prefix[0])
print("subarrays summing to 3:", count_subarrays_with_sum([1, 2, 1, -1, 3, 0], 3))
print("product except self:", product_except_self([1, 2, 3, 4]))

days 1-3: 26500
days 0-5: 42500
subarrays summing to 3: 7
product except self: [24, 12, 8, 6]

function buildPrefix(nums) {
  const prefix = [0];
  for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);
  return prefix;
}

function countSubarraysWithSum(nums, k) {
  const seen = new Map([[0, 1]]);
  let total = 0, count = 0;
  for (const x of nums) {
    total += x;
    count += seen.get(total - k) ?? 0;
    seen.set(total, (seen.get(total) ?? 0) + 1);
  }
  return count;
}

function productExceptSelf(nums) {
  const n = nums.length;
  const out = new Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {        // product of everything to the left
    out[i] = left;
    left *= nums[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {   // times everything to the right
    out[i] *= right;
    right *= nums[i];
  }
  return out;
}

const steps = [4000, 8000, 6500, 12000, 3000, 9000];
const prefix = buildPrefix(steps);
console.log("days 1-3:", prefix[4] - prefix[1]);
console.log("days 0-5:", prefix[6] - prefix[0]);
console.log("subarrays summing to 3:", countSubarraysWithSum([1, 2, 1, -1, 3, 0], 3));
console.log("product except self:", JSON.stringify(productExceptSelf([1, 2, 3, 4])).replaceAll(",", ", "));

days 1-3: 26500
days 0-5: 42500
subarrays summing to 3: 7
product except self: [24, 12, 8, 6]

Common mistakes

• Off-by-one errors. Starting prefix with a 0 makes the formula prefix[j + 1] - prefix[i] work for every range, including ones starting at 0.
• Forgetting {0: 1} in the subarray count. It stands for "the empty prefix", so subarrays starting at index 0 are counted.
• Updating the map before counting. Count total - k first, then record total; otherwise with k = 0 every position counts itself.
• Using a sliding window when numbers can be negative. That's exactly when prefix sums are needed.

Practice

• Product of Array Except Self (medium): prefix and suffix products, no division.
• Revisit Two Sum: "subarray sum = k" is Two Sum on running totals.

Key points

• prefix[i] = sum of the first i items; range sum = prefix[j+1] - prefix[i].
• O(n) once to build, then O(1) per range question.
• Running total + map of earlier totals counts subarrays with sum k, negatives included.
• The same "before × after" idea gives product-except-self without division.