Prefix Sums

Prefix Sums let you query subarray sums quickly after one pass.

Key Ideas

• Build pref[i] = sum of first i elements.
• Subarray sum [l..r] is pref[r+1] - pref[l].
• Hash map of prefix sums helps count subarrays with a target sum.