Prefix Sums

Pre-compute running totals once, then answer "what is the sum from i to j?" instantly — a classic interview speed-up. Level up: count subarrays that sum to k If two prefix sums differ by k, the numbers between them sum to k. Remember how many times each prefix sum was seen: