Pre-compute cumulative sums so that any subarray sum query is answered in O(1).

Data Flow

arr = [3, 1, 4, 1, 5, 9, 2, 6]

prefix[i] = arr[0] + ... + arr[i-1]   (length N+1, prefix[0]=0)

[i, j] sum = prefix[j+1] - prefix[i]

When to use

• “Sum of subarray from i to j”.
• “Subarray sum == K” (combine with hashmap of running sums).
• 2-D prefix sum for rectangle sums.

Code

def make_prefix(arr):
    ps = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        ps[i+1] = ps[i] + x
    return ps
 
def range_sum(ps, i, j):
    return ps[j+1] - ps[i]
 
# count subarrays with sum == k
def subarray_sum(nums, k):
    from collections import defaultdict
    ps = 0; count = 0; seen = defaultdict(int, {0: 1})
    for n in nums:
        ps += n
        count += seen[ps - k]
        seen[ps] += 1
    return count

Pitfalls

• Off-by-one on prefix[j+1] - prefix[i] vs prefix[j] - prefix[i-1]. Pick one convention.
• For 2D prefix sum, careful with inclusive/exclusive corners.

Analogy

A running ledger: to find how much you spent last week, subtract the balance at the start of the week from today.

Interview tip: Combine prefix sum with a hashmap whenever the question mentions ”== K” — O(N) trick, memorise it.