Prefix Sum

Prefix Sum

OVERVIEW

Prefix Sum is a preprocessing technique used to efficiently answer range-based
queries on arrays.

The idea is simple:

• Precompute cumulative sums
• Use them to answer subarray sum queries in O(1)

Instead of recomputing sums repeatedly, we reuse previously computed results.

WHEN TO USE

Use Prefix Sum when:

• You are asked for sum of multiple subarrays
• Queries involve ranges [L, R]
• You want to reduce repeated work
• The array is static (no frequent updates)

TIME & SPACE

Preprocessing Time : O(N)
Query Time : O(1)
Space Complexity : O(N)

CORE IDEA

Given an array:
arr = [a0, a1, a2, a3, ...]

Build prefix sum array:
prefix[0] = 0
prefix[i] = a0 + a1 + ... + a(i-1)

Then:
Sum of subarray [L, R] =
prefix[R + 1] - prefix[L]

EXAMPLE 1: Build Prefix Sum Array

def build_prefix_sum(arr):
prefix = [0] * (len(arr) + 1)

for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

return prefix

EXAMPLE 2: Range Sum Query

Problem:
Find sum of elements between index L and R (inclusive).

Formula:
sum(L, R) = prefix[R + 1] - prefix[L]

def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]

EXAMPLE 3: Subarray Sum Equals K

Problem:
Count the number of subarrays whose sum equals k.

Key Insight:
If:
prefix[j] - prefix[i] = k
Then:
prefix[i] = prefix[j] - k

Use a hashmap to track prefix sum frequencies.

def subarray_sum_equals_k(nums, k):
prefix_sum = 0
count = 0
freq = {0: 1}

for num in nums:
    prefix_sum += num

    if prefix_sum - k in freq:
        count += freq[prefix_sum - k]

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

return count

EXAMPLE 4: Maximum Sum Subarray of Size K

Problem:
Find maximum sum of any subarray of size k.

This is a prefix-sum-based solution (sliding window optimized version exists).

def max_sum_subarray_k(arr, k):
prefix = build_prefix_sum(arr)
max_sum = float('-inf')

for i in range(len(arr) - k + 1):

    current_sum = prefix[i + k] - prefix[i]

    max_sum = max(max_sum, current_sum)

return max_sum

IDENTIFICATION CHECKLIST

Ask these questions:

• Are multiple range queries involved?
• Is the array static?
• Do I need fast subarray sum computation?
• Can subtraction of cumulative values help?

If yes, Prefix Sum is the correct approach.

COMMON PITFALLS

• Off-by-one errors in indexing
• Forgetting to add initial 0 in prefix array
• Using prefix sum on frequently updated arrays
• Assuming only positive numbers (prefix works with negatives too)

SUMMARY

• Precompute once, query many times
• Range sum in O(1)
• Powerful when combined with hash maps
• Foundational technique for many advanced problems