Array & StringBeginner
Prefix Sum
Precompute cumulative sums to answer range sum queries in O(1) time after O(n) preprocessing.
Problem: Range Sum Query
Original array: [1, 2, 3, 4, 5]. Build a prefix sum array to answer range queries in O(1) time.
0
i
Initialize prefix array
Create prefix array with prefix[0] = 0. prefix[i] will store sum of arr[0...i-1].
Step 1/7
Speed:
When to Use
- Multiple range sum queries
- Subarray sum equals target
- Count subarrays with property based on cumulative values
Key Indicators
- Range sum queries
- Subarray sum equals K
- Cumulative computation
- Multiple queries on same array
Complexity
Time
O(n) build, O(1) query
Space
O(n)
Common Problems
Range Sum QuerySubarray Sum Equals KContiguous ArrayProduct of Array Except SelfRange Sum Query 2D – Immutable
Code
prefix[0] = 0
for i in range(n):
prefix[i+1] = prefix[i] + arr[i]
# sum of arr[l..r] = prefix[r+1] - prefix[l]Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)