The idea
Let P[i] = a[1] + … + a[i] with P[0] = 0. Then the sum of a[l..r] is P[r] − P[l−1]: one subtraction instead of a loop.
To count subarrays with some property, fix the right end r and ask how many earlier prefixes match it. A map of prefix values seen so far answers that in one pass.
A bitset packs bits into machine words, so AND, OR and counting run 64 positions at a time. It turns some O(n²) or O(n³) loops over 0/1 data into something fast enough.
Sample problem
560. Subarray Sum Equals K ↗ Medium
Count the contiguous subarrays whose sum equals k. The numbers may be negative.
nums = [1,2,3,-2,2], k = 3 output = 4 ([1,2], [3], [2,3,-2], [3,-2,2])
Why the solution works
With prefix sums, the sum of nums[l..r] is P[r] − P[l−1]. So a subarray ending at r sums to k exactly when some earlier prefix equals P[r] − k.
Walk the array once keeping the current prefix sum and a map that counts how often each prefix value has occurred. At each position, add the count of sum − k to the answer.
Two pointers would fail here because negative numbers make the window sum non-monotone. Prefix sums do not care about signs.
Complexity: O(n) time on average, O(n) memory.
Watch out
- Use 1-based positions with
P[0] = 0to avoid off-by-one errors at the left edge. - Sums overflow
intquickly: uselong long. - When counting with a map, put the empty prefix
P[0]in before the loop.