Prefix Sum

A Prefix Sum array stores cumulative totals so that any subarray sum can be computed in $O(1)$ after $O(N)$ preprocessing. Without it, each query costs $O(N)$ ; with it, unlimited queries each cost $O(1)$ .

Building the Prefix Sum Array

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)
    for i, val in enumerate(nums):
        prefix[i + 1] = prefix[i] + val
    return prefix

prefix[i] = sum of nums[0..i-1]. The extra 0 at the start simplifies range queries.

Range Sum Query

Sum of nums[l..r] (inclusive):

range_sum = prefix[r + 1] - prefix[l]

That's it. One subtraction, $O(1)$ .

Problem: Subarray Sum Equals K

Count subarrays whose sum equals k.

Naive: try every pair (l, r) → $O(N^2)$ .

With prefix sum + hash map: for each r, we want the number of l values where prefix[r] - prefix[l] == k, i.e., prefix[l] == prefix[r] - k. Keep a running count of prefix sums seen so far.

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1   # empty prefix
    total = 0
    running = 0

    for num in nums:
        running += num
        total += count[running - k]   # how many prior prefixes give sum k
        count[running] += 1

    return total

Time: $O(N)$ . Space: $O(N)$ .

2D Prefix Sum

For grid problems, precompute a 2D prefix sum to answer rectangle sum queries in $O(1)$ :

# prefix[r][c] = sum of all cells in the rectangle (0,0) to (r-1,c-1)
for r in range(1, rows + 1):
    for c in range(1, cols + 1):
        prefix[r][c] = (grid[r-1][c-1]
                        + prefix[r-1][c]
                        + prefix[r][c-1]
                        - prefix[r-1][c-1])

# Query: sum of rectangle (r1,c1) to (r2,c2)
rect_sum = (prefix[r2+1][c2+1]
            - prefix[r1][c2+1]
            - prefix[r2+1][c1]
            + prefix[r1][c1])

When Do I Use This?

Grid or 1D array prefix sum operations.
Need to find subarrays with a given sum → prefix sum + hash map.
Sliding window cannot apply because the window is not contiguous in constraint space.

Practice Problems

Done	Question	Difficulty
	Count Vowels in Substrings	Medium
	Subarray Sum Equals K	Medium