/
Prefix Sum
Precompute cumulative sums in O(n) time, then answer any range-sum query in O(1). A classic interview pattern for problems about subarray sums.
Algorithm Pattern
O(1) Query
What & Why
Given an array nums, the prefix sum array prefix stores the cumulative sum: prefix[i] = nums[0] + nums[1] + ... + nums[i-1]. The sum of any subarray nums[l..r] is then just prefix[r+1] - prefix[l] — a single subtraction.
Building the prefix array takes O(n). Every query after that is O(1). If you'll ask many range-sum questions on the same input, this is the right tool.
Visualization
Code (Python)
Python
def build_prefix(nums):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return prefix
def range_sum(prefix, l, r):
return prefix[r + 1] - prefix[l]
# Example
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums) # O(n) preprocessing
print(range_sum(prefix, 2, 5)) # 4+1+5+9 = 19, in O(1)
Complexity
| Operation | Time | Space |
|---|---|---|
| Build prefix array | O(n) | O(n) |
| Range sum query | O(1) | O(1) |
| Update single element | O(n) rebuild | — |
Note: If updates are common, look into Binary Indexed Trees / Segment Trees instead — they give O(log n) update and O(log n) query.