← Back to the arrays page
Prefix-Sum & Difference Arrays
Preprocess once, answer range questions forever. Prefix sums answer range-sum queries in O(1); difference arrays apply range updates in O(1).
What to know
- prefix[i] = prefix[i−1] + arr[i]; sum(l..r) = prefix[r] − prefix[l−1].
- Difference array: add v at l, subtract v after r, then prefix-sum to materialize.
- 2D prefix sums answer rectangle sums with four lookups (inclusion-exclusion).
- Prefix sum + hash map solves "subarray sum equals K" in one pass.
In the wild: Analytics dashboards (sum over date range), flight booking seat-count changes, image integral tables.
Algorithms to reach for
Range-sum query
O(1) queryInstant subarray totals after O(n) prep
Subarray sum = K (prefix + hashmap)
O(n)Count subarrays hitting a target
Range update via difference array
O(1) per updateBulk +v on many ranges, one materialize
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.