Prefix Sum

Precompute cumulative totals once so any range query answers in O(1) — and combine with a hash map to count subarrays hitting a target.

Key ideas

  • —prefix[i] stores the sum of everything before index i; a range sum is one subtraction.
  • —Build the prefix array in O(n), then answer each range query in O(1).
  • —Pairing prefix sums with a hash map counts subarrays with a given sum in one pass.

Range queries in constant time

If prefix[i] is the sum of the first i elements, then the sum of any range [l, r) is prefix[r] − prefix[l]. One O(n) preprocessing pass turns every later range query into a single subtraction. The same idea generalizes to products (Product of Array Except Self builds prefix and suffix products) and to two dimensions for submatrix sums.

Prefix sums plus a hash map

To count subarrays summing to k, walk left to right tracking the running prefix sum and a map of how many times each prefix value has occurred. At each index, the number of valid subarrays ending here equals the count of prefix − k seen so far. This converts an O(n²) double loop into a single O(n) pass.

Practice this

Sources

← All lessonsNext: Intervals →