Prefix Sum —
Preprocess once. Query in O(1).
The prefix sum technique trades O(n) preprocessing for O(1) range queries. Build a running total array once, then answer "what is the sum of elements from index L to R?" in a single subtraction — no loop. Watch the prefix array build up element by element on LearnBug and see every query resolve instantly.
What is a Prefix Sum?
A prefix sum array prefix[i] stores the sum of all elements from index 0 up to index i. Once built, the sum of any subarray from index L to R is just prefix[R] - prefix[L-1] — one subtraction regardless of how large the range is. This turns an O(n) per-query problem into O(1) per query after an O(n) setup.
Why visualization changes everything
The subtraction trick feels like magic until you see it. On LearnBug, you watch the prefix array build cell by cell — each entry absorbing the previous total. Then when you make a range query, two cells light up and their difference instantly shows the subarray sum. The "why" behind the formula becomes obvious the moment you watch it.
Building the prefix sum array
Original array: [3, 1, 4, 1, 5, 9, 2]
Original array
Seven elements. To answer any range query with a loop costs O(n) each time. With prefix sum we pay O(n) once and get O(1) forever.
prefix[0] = nums[0] = 3
The first prefix entry is just the first element. Running total starts here.
prefix = [3, ?, ?, ?, ?, ?, ?]
prefix[i] = prefix[i-1] + nums[i]
Each entry absorbs the previous running total: 3, 3+1=4, 4+4=8, 8+1=9, 9+5=14, 14+9=23, 23+2=25.
prefix = [3, 4, 8, 9, 14, 23, 25]
Answering range queries in O(1)
prefix = [3, 4, 8, 9, 14, 23, 25]. Formula: sum(L, R) = prefix[R] - prefix[L-1]
Sum of indices 2 to 4 = ?
sum(2, 4) = prefix[4] - prefix[1] = 14 - 4 = 10. Manual check: 4 + 1 + 5 = 10 ✓. One subtraction — no loop.
14 - 4 = 10 ✓
Sum of entire array (indices 0 to 6)
sum(0, 6) = prefix[6] - prefix[-1]. When L = 0, there's no prefix[-1] — use 0 instead. So answer = 25 - 0 = 25. This is why some implementations use a 1-indexed prefix array with prefix[0] = 0.
25 - 0 = 25 ✓
Prefix sum in code
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1) # 1-indexed: prefix[0] = 0
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, left, right):
# sum of nums[left..right] (both inclusive, 0-indexed)
return prefix[right + 1] - prefix[left]
# Example usage:
nums = [3, 1, 4, 1, 5, 9, 2]
prefix = build_prefix(nums)
print(range_sum(prefix, 2, 4)) # → 10 (4+1+5)
print(range_sum(prefix, 0, 6)) # → 25 (entire array)Time & Space Complexity
Where prefix sum shows up
Multiple range sum queries
Any problem with repeated "sum from L to R" queries — range sum query, subarray sum equals k — screams prefix sum.
Subarray sum equals K
Count subarrays summing to k using prefix sum + hash map. Check how many times prefix[i] - k has appeared before — O(n) total.
2D prefix sum (matrix)
Extend to 2D for O(1) rectangular region sum queries on a grid. Used in image processing and competitive programming.
Difference array (reverse prefix sum)
The inverse: apply range updates in O(1) and query point values in O(n). Used for "add value v to all elements from L to R" problems.
Frequently asked questions
Why does the formula sum(L, R) = prefix[R] - prefix[L-1] work?
prefix[R] is the sum of all elements from index 0 to R. prefix[L-1] is the sum of all elements from index 0 to L-1. Subtracting removes the elements before L — leaving only the sum from L to R. It's like cancelling out the "left overhang" from both totals.
Why use a 1-indexed prefix array with prefix[0] = 0?
It handles the edge case where L = 0 cleanly. Without it, prefix[L-1] would be prefix[-1] — invalid. With a sentinel 0 at index 0, the formula prefix[R+1] - prefix[L] works for all L including 0, with no special case needed.
Can prefix sum handle updates to the original array?
Not efficiently. If you update a single element, you'd need to rebuild the entire prefix array in O(n). For problems with both updates and range queries, use a Fenwick Tree (Binary Indexed Tree) or Segment Tree — both support O(log n) updates and O(log n) queries.
What is the connection between prefix sum and Kadane's algorithm?
The maximum subarray sum can be rephrased as: find the maximum value of prefix[j] - prefix[i] for j > i. Kadane's solves this in O(n) by tracking the minimum prefix seen so far as it scans. Both are fundamentally about running totals — prefix sum makes the relationship explicit.
What are common interview problems using prefix sum?
Subarray Sum Equals K (LC 560), Range Sum Query (LC 303), Product of Array Except Self (LC 238 — uses prefix and suffix products), Find Pivot Index (LC 724), Maximum Average Subarray (LC 643), and Running Sum of 1D Array (LC 1480). Prefix sum is one of the most frequently tested array techniques after two pointer and sliding window.
Watch the prefix array build on your own input
Paste your array into LearnBug and see every prefix value compute step by step, then watch range queries resolve instantly.