Internship← Competitive Programming learning pathCompetitive Programming · Module 5 of 10
Prefix sums and hashing
Answer range queries and lookups in constant time.
📖 Key ideas
- Prefix sum p[i] = a[0] + ... + a[i-1]; sum of l..r = p[r+1] - p[l].
- 2D prefix sums answer rectangle sums.
- Difference arrays apply many range updates in O(1) each.
- Hash maps (unordered_map, dict) count frequencies in O(1) average.
- Count subarrays with sum K using prefix sums plus a hash map.
💡 Real-life example: A prefix sum is a running bank balance: the spend between two dates is just the difference of balances.
Prefix sumRunning total array
Difference arrayCheap range updates
Hash mapKey-value lookup in O(1) average
Frequency countHow often each value appears