Prefix sums
A prefix sum array precomputes cumulative totals so you can answer any range-sum query in O(1). Define prefix[i] as the sum of the first i elements; then the sum of the range [i, j) is just prefix[j] - prefix[i].
# prefix[k] = a[0] + a[1] + ... + a[k-1] prefix = [0] * (len(a) + 1) for i in range(len(a)): prefix[i + 1] = prefix[i] + a[i] # sum of a[i..j] inclusive: range_sum = prefix[j + 1] - prefix[i]
Building the prefix array is a single O(n) pass; each query afterward is O(1). This turns 'answer Q range-sum queries' from O(n*Q) into O(n + Q).
Example: count subarrays summing to k
A subarray (i, j] sums to k exactly when prefix[j] - prefix[i] == k, i.e. prefix[i] == prefix[j] - k. So sweep left to right keeping a hash map of prefix-sum counts seen so far; at each j add the count of prefix[j] - k. That is O(n) time and combines two patterns at once. Seed the map with {c}{0: 1}{/c} — the empty prefix — or you'll miss every subarray that starts at index 0. Forgetting the seed is the #1 bug in this problem.
O(1).◆ Lock it in
- Prefix sums answer any range sum in
O(1)after anO(n)build. sum(i..j) = prefix[j+1] - prefix[i]— subtract, do not re-add.- Prefix-sum + hash map counts subarrays summing to k in
O(n).