Prefix sums

Prefix sums let you get the sum of any range with one subtraction. Set P[0] = 0 and P[i + 1] = P[i] + a[i]. Then the sum of a[l] through a[r − 1] is P[r] − P[l]. For [2, 4, 1], P is [0, 2, 6, 7], and the sum of the last two numbers is 7 − 2 = 5. The leading zero stands for "nothing added yet", so ranges that start at index 0 need no special case.

For many range-sum queries on a list that doesn't change, this turns O(length) work per query into O(1), after O(n) time and space to build P. To find subarrays that sum to k, rearrange P[r] − P[l] = k into P[l] = P[r] − k. Now you're counting earlier prefix sums with a specific value, which a hash map does.

pub fn count_sum(nums: &[i32], k: i64) -> i64 {
    use std::collections::HashMap;
    let mut counts = HashMap::from([(0_i64, 1_i64)]);
    let (mut prefix, mut answer) = (0_i64, 0_i64);
    for &x in nums {
        prefix += i64::from(x);
        if let Some(needed) = prefix.checked_sub(k) {
            answer += counts.get(&needed).copied().unwrap_or(0);
        }
        *counts.entry(prefix).or_insert(0) += 1;
    }
    answer
}

Before each lookup, counts holds the prefix sums strictly before the current position. Looking up before inserting means that, when k is zero, you don't count an empty subarray. For [1, -1, 1] and k = 1, the answer is 3. A set instead of counts would lose how many times each prefix sum appeared.

This works with negative numbers, unlike a sliding window. It takes O(n) time on average and O(n) space. The code assumes the sums and the count fit in i64.

Prefix sums work for more than addition. For XOR, a range is P[r] XOR P[l]. A running minimum can't give you the minimum of any range, though, because there's no way to "subtract" a minimum. Products need care with zeros, overflow, and division.

A difference array works the other way. To add x to every element in a range from l up to (not including) r, add x at index l and subtract x at index r. One prefix sum pass at the end rebuilds every value. This helps when you can collect all the updates before you need any answer.

Practice: LC 303 Range Sum Query Immutable, LC 560 Subarray Sum Equals K, LC 974 Subarray Sums Divisible by K, LC 1109 Corporate Flight Bookings, LC 238 Product of Array Except Self. For divisibility, make negative remainders positive, and make sure the divisor isn't zero.

Check your understanding: Why does the hash map start with one empty prefix? What do you need to store to count ranges, and what to find the longest one? Why do single-value updates make a plain prefix sum array expensive to keep up to date?