Prefix Sum

Prefix sum is preprocessing that makes range sum queries instant. Instead of summing elements every time, you precompute cumulative sums. Then any range sum is just one subtraction.

The Core Idea

Build an array where prefix[i] = sum of all elements from 0 to i-1. Then sum(i, j) = prefix[j+1] - prefix[i]. O(n) preprocessing, O(1) per query.

Building Prefix Sum

def buildPrefixSum(nums):
    prefix = [0]  # Start with 0
    for num in nums:
        prefix.append(prefix[-1] + num)
    return prefix

# Query sum from index i to j (inclusive)
def rangeSum(prefix, i, j):
    return prefix[j + 1] - prefix[i]

Classic: Subarray Sum Equals K

Count subarrays that sum to k:

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}  # prefix_sum -> count

    for num in nums:
        prefix_sum += num

        # If prefix_sum - k exists, we found subarrays
        if prefix_sum - k in seen:
            count += seen[prefix_sum - k]

        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1

    return count