DSA Notes

Data Structures

Prefix Sums & Bitset

Precompute running totals to answer range sums in O(1).

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] = 0 to avoid off-by-one errors at the left edge.
  • Sums overflow int quickly: use long long.
  • When counting with a map, put the empty prefix P[0] in before the loop.
Watch it run

Try your own input

Practise on LeetCode