Day 6: Prefix Sums Explained Simply
What if you could calculate the total sum of any slice of an array with a million numbers in a single millisecond without looping through them ever again?
In 30 Seconds
A Prefix Sum is a precomputed helper array where each entry stores the cumulative total of all elements up to that point. Instead of re-summing numbers over and over whenever someone asks for a range total, you do all the addition once upfront. Any range sum between index L and index R can then be retrieved in exactly one subtraction: prefix[R] - prefix[L - 1]. This turns expensive range queries from an $O(N)$ chore into an instantaneous $O(1)$ lookup.
The Real-World Analogy: The Odometer in Your Car
Imagine you are driving on a cross-country highway trip from Boston to Miami. Along the road, you pass mileage markers. Your dashboard has an odometer that records the total lifetime miles driven since the car left the factory.
If you want to know how many miles you drove between Richmond, Virginia (mile marker 400) and Savannah, Georgia (mile marker 750), you don't re-measure every single mile of highway between them one by one. You simply look at your odometer in Savannah (750) and subtract your odometer reading from Richmond (400):
750 - 400 = 350 miles
That odometer is a prefix sum. It continuously tallies everything from day zero so that any trip segment can be computed with a single subtraction.
Picture This
Here is how an original array translates into its cumulative prefix sum array:
Index: 0 1 2 3 4
Original Array: [ 3 | 5 | 2 | 8 | 1 ]
| | | | |
Accumulation: (3) (3+5) (8+2) (10+8) (18+1)
v v v v v
Prefix Array: [ 3 | 8 | 10 | 18 | 19 ]
Now, watch how querying the sum between Index 1 and Index 3 works without looping:
Query: Sum of slice [Index 1 .. Index 3] (Values: 5 + 2 + 8 = 15)
Prefix Array: [ 3 | 8 | 10 | 18 | 19 ]
^ ^
prefix[L-1] prefix[R]
(prefix[0]) (prefix[3])
= 3 = 18
Formula: prefix[R] - prefix[L - 1]
= 18 - 3
= 15 (Instant constant-time answer!)
How It Actually Works
- Allocate a Precomputation Table: Create a new array of the same length (or length $N + 1$ with a leading zero to handle edge cases cleanly).
- Seed the Initial Element: Set
prefix[0] = arr[0]. The sum of the first element is simply itself. - Build Cumulative Totals: Loop from index
1toN - 1. For each indexi, calculateprefix[i] = prefix[i - 1] + arr[i]. Becauseprefix[i - 1]already holds the sum of everything prior, you only add one number at each step. - Answer Range Queries in $O(1)$: When queried for range
[L, R]:- If
L == 0, the answer is directlyprefix[R]. - If
L > 0, the answer isprefix[R] - prefix[L - 1].
- If
Show Me The Code
Here is a clean, fully-commented Python implementation showing how to construct and query a prefix sum array.
# Day 6: Prefix Sum Array Pattern in Python
class PrefixSum:
def __init__(self, arr):
"""
Builds the prefix sum array in O(N) time.
We use an extra slot at index 0 (1-based prefix table)
to elegantly eliminate boundary checks when L = 0.
"""
self.n = len(arr)
# prefix[i] stores the sum of arr[0 ... i - 1]
self.prefix = [0] * (self.n + 1)
for i in range(self.n):
self.prefix[i + 1] = self.prefix[i] + arr[i]
def query_range(self, left, right):
"""
Returns the sum of arr[left ... right] inclusive.
Runs in O(1) constant time!
"""
if left < 0 or right >= self.n or left > right:
raise IndexError("Invalid range query bounds.")
# Range sum is prefix[right + 1] - prefix[left]
return self.prefix[right + 1] - self.prefix[left]
# --- Quick Test Execution ---
if __name__ == "__main__":
nums = [3, 5, 2, 8, 1]
tracker = PrefixSum(nums)
print("Original Array:", nums)
print("Internal Prefix Array:", tracker.prefix)
# Query sum of range index 1 to index 3 (5 + 2 + 8 = 15)
print("Sum of range [1, 3]:", tracker.query_range(1, 3))
# Query sum of range index 0 to index 2 (3 + 5 + 2 = 10)
print("Sum of range [0, 2]:", tracker.query_range(0, 2))
Dry Run
Let's trace building the prefix sum array for arr = [4, 7, 2]:
| Step | Loop Index i |
Calculation | State of prefix Array |
|---|---|---|---|
| 1 | Init | Pre-fill zeros | [0, 0, 0, 0] |
| 2 | i = 0 (val: 4) |
prefix[1] = prefix[0] + 4 = 0 + 4 |
[0, 4, 0, 0] |
| 3 | i = 1 (val: 7) |
prefix[2] = prefix[1] + 7 = 4 + 7 |
[0, 4, 11, 0] |
| 4 | i = 2 (val: 2) |
prefix[3] = prefix[2] + 2 = 11 + 2 |
[0, 4, 11, 13] |
Querying range(1, 2) computes prefix[3] - prefix[1] = 13 - 4 = 9 (matching 7 + 2 = 9).
Speed & Memory
By investing $O(N)$ work and memory up front, every future query executes in an eye-blink:
| Operation | Naive Approach | Prefix Sum Approach | Why? |
|---|---|---|---|
| Preprocessing Time | $O(1)$ (No preprocessing) | $O(N)$ | Single pass through the input array to sum items. |
| Per-Query Time | $O(N)$ | $O(1)$ | A single subtraction replaces looping through elements. |
| Space Complexity | $O(1)$ | $O(N)$ | Requires storing an auxiliary array of size $N + 1$. |
Where You'll See It In Real Life
- Financial Accounting & Ledger Balancing: Wall Street ledger software calculates cumulative cash balances over arbitrary fiscal quarters in constant time without scanning individual debit lines.
- Computer Graphics & Blur Filters: 2D prefix sums (Summed Area Tables) allow image editing software to calculate local area averages instantly for box blur and depth-of-field filters.
- E-Commerce Sales Dashboards: Analytics platforms query sales volumes between custom date ranges on the fly using precomputed prefix sums aggregated per hour.
Traps To Avoid
- Trap 1: Off-by-one errors when querying index
0.
Fix: Use an $(N + 1)$ sized prefix array with an initial0at index0to avoid specialif L == 0branch conditions. - Trap 2: Integer overflow in low-level languages (like C++ or Java).
Fix: Store prefix sums in 64-bit integers (long longorlong) because summing thousands of integers can exceed standard 32-bit limits. - Trap 3: Using Prefix Sums on arrays with frequent updates.
Fix: If data changes frequently, updating a prefix sum takes $O(N)$. Use a Fenwick Tree (Binary Indexed Tree) or Segment Tree instead for dynamic datasets.
Practice Problems
- Easy: Find the equilibrium index of an array—an index where the sum of lower indices equals the sum of higher indices. (Hint: Use total sum minus prefix sum.)
- Medium: Given an array of integers and an integer $K$, return the total number of continuous subarrays whose sum equals $K$. (Hint: Combine prefix sums with a hash map!)
- Hard: Given a 2D matrix of numbers, implement a class that answers the sum of any sub-rectangle in $O(1)$ time. (Hint: Extend prefix sums to two dimensions using inclusion-exclusion principle.)
TL;DR
- Prefix Sums trade $O(N)$ extra memory up front for blazing fast $O(1)$ range queries.
- Any range sum from $L$ to $R$ equals
prefix[R] - prefix[L - 1]. - Ideal for static datasets with heavy query loads, like reporting dashboards and image processing.
References Consulted
- GeeksforGeeks - Prefix Sum Array Implementation & Applications — referenced for verification — all content above is original.
- CP-Algorithms - Range Sum Queries and Fenwick Trees — referenced for verification — all content above is original.
Covered Log Update
Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums]