Array and string patterns
Prefix sums
Turn range calculations into subtraction.
Understand the problem
Define prefix[0]=0 and prefix[i+1]=prefix[i]+a[i]. Then the sum over [l,r) is prefix[r]-prefix[l]. A frequency map of earlier prefix sums counts subarrays with a target sum.
Make it concrete
For [2, -1, 3], prefix is [0, 2, 1, 4]. The sum from index 1 through 2 is 4-2=2.
Trade-offs and pitfalls
Use a sufficiently wide numeric type to avoid overflow.
Check your understanding
Why must the map initially contain prefix sum zero once?
Practice this topic