Prefix sums
Many range-sum queries on a fixed array, or counting subarrays with a given sum (with a hash map).
High interview relevanceRoadmap: Intermediate
| Time | O(n) to build; O(1) per range sum |
|---|---|
| Space | O(n) |
Why it costs this much
prefix[j] − prefix[i] equals the sum of items i through j − 1, so each query is a single subtraction.
Code
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x) # O(n) to build
def range_sum(i, j): # sum of nums[i:j]
return prefix[j] - prefix[i] # O(1) per queryCommon pitfalls
Updating the array invalidates the table; use a Fenwick tree if updates are frequent. Off-by-one mistakes around the leading 0 are common.
Operation by operation
| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Prefix sums | O(n) build, O(1) query | O(n) build, O(1) query | O(n) build, O(1) query | O(n) |
Prefix sums. The array is not modified between queries. Updates make this O(n) each. Use a Fenwick tree or segment tree for mixed updates and queries.