Prefix Sums: Efficient Range Summation
Prefix sums are one of the most powerful tools for problems that involve repeated sum calculations over subarrays or substrings. With a single pass of preprocessing, you can turn a brute-force O(n) sum into an instant O(1) lookup!
What Is a Prefix Sum?
A prefix sum array stores the cumulative sum of elements from the beginning up to each index.
If arr = [2, 4, 6, 8], then the prefix sum array is:
prefix = [2, 6, 12, 20]
This means:
- prefix[0] = arr[0]
- prefix[1] = arr[0] + arr[1]
- prefix[2] = arr[0] + arr[1] + arr[2]
- ...
With this structure, the sum of any subarray arr[i:j] can be found using:
sum = prefix[j] - prefix[i - 1]
Visualizing Prefix Sums
This diagram shows how each prefix value is built from previous values.
Example: Sum of Elements in a Range
Say you are given an array and asked multiple queries like: "What is the sum of elements from index i to j?"
❌ Brute-force Approach
def range_sum(arr, i, j):
return sum(arr[i:j+1])
This is simple but inefficient — takes O(n) time per query.
✅ Prefix Sum Approach
def build_prefix_sums(arr):
prefix = [0] * len(arr)
prefix[0] = arr[0]
for i in range(1, len(arr)):
prefix[i] = prefix[i-1] + arr[i]
return prefix
def range_sum(prefix, i, j):
if i == 0:
return prefix[j]
return prefix[j] - prefix[i-1]
Now, range queries take O(1) time after O(n) preprocessing.
🔍 When to Use Prefix Sums
Prefix sums are ideal for problems that involve:
- Repeated range sum queries
- Counting within subarrays or substrings
- Analyzing patterns in cumulative data
Real-World Applications
| Domain | Use Case |
|---|---|
| Analytics | Cumulative user activity, traffic analysis |
| Finance | Running totals, rolling revenue sums |
| Competitive Coding | Range queries, subarray problems |
| Genomics | GC content in DNA substrings |
| Game Development | Scoring over levels/time intervals |
Summary
Prefix sums help you avoid repeated work by turning a linear operation into constant-time. It's an essential tool in your algorithmic toolbox for array processing.