Prefix Sum

Pre-compute cumulative sums to answer range-sum queries in O(1) instead of O(n).

Identify this pattern when:

• "Sum of elements between index i and j"
• "Subarray sum equals K"
• "Count subarrays with property X"
• Need to repeatedly query sums over ranges

---

Core Template

# Build prefix sum array
def build_prefix(nums: list[int]) -> list[int]:
    n = len(nums)
    prefix = [0] * (n + 1)     # prefix[0] = 0 (sentinel)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

# Range sum query [l, r] inclusive, O(1)
def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

# Example
nums   = [1, 2, 3, 4, 5]
prefix = [0, 1, 3, 6, 10, 15]
# sum(nums[1:3]) = nums[1] + nums[2] = 2 + 3 = 5
# = prefix[4] - prefix[1] = 10 - 1... wait
# [1,3] inclusive: prefix[4] - prefix[1] = 10 - 1 = 9... no
# sum([2,3,4]) = prefix[4] - prefix[1] = 10-1 = 9 ✓ (index 1 to 3)

Formula: sum(i, j) = prefix[j+1] - prefix[i]

---

Subarray Sum Equals K

Classic hashmap + prefix sum. Find count of subarrays with sum = k.

def subarraySum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    seen = {0: 1}  # prefix_sum → frequency; 0 appears once (empty prefix)

    for num in nums:
        prefix += num
        # if (prefix - k) was seen before, then subarray from that point sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1

    return count

Why {0: 1}? If prefix == k, then prefix - k == 0, which should count the subarray from the start.

---

Product of Array Except Self (no division)

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n

    # left pass: result[i] = product of all elements to the LEFT
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # right pass: multiply by product of all elements to the RIGHT
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

---

Range Sum Query — Mutable (Binary Indexed Tree)

For static array: prefix sum is enough. For mutable (updates + queries), use Binary Indexed Tree.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] + list(itertools.accumulate(nums))

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

---

2D Prefix Sum

def build_2d_prefix(matrix):
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (matrix[i-1][j-1]
                           + prefix[i-1][j]
                           + prefix[i][j-1]
                           - prefix[i-1][j-1])
    return prefix

# Sum of submatrix (r1,c1) to (r2,c2)
def query_2d(prefix, r1, c1, r2, c2):
    return (prefix[r2+1][c2+1]
            - prefix[r1][c2+1]
            - prefix[r2+1][c1]
            + prefix[r1][c1])

---

Problems & Patterns

---

Kadane's Algorithm — Max Subarray Sum

Different from prefix sum but fits the arrays topic:

def maxSubArray(nums: list[int]) -> int:
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)  # extend or restart
        max_sum = max(max_sum, current)
    return max_sum

---

Time & Space

---

Related

• [[DSA/Data Structures/Hash Map]] — hashmap for prefix sum frequency
• [[DSA/DSA Techniques for Interviews/03. Sliding Window]] — alternative for contiguous subarray problems
• [[DSA/DSA Techniques for Interviews/02. Two Pointers]] — pairs with prefix for some problems