Prefix Sums & Binary Search on Answer

Why this module exists

Two of the most reliable patterns in interviews:

• Prefix sums for range/subarray queries
• Binary search on the answer when feasibility is monotonic

Prefix sums (range queries)

Define: pref[i] = nums[0] + ... + nums[i-1] (length i prefix)

Then any range sum is: sum(l..r) = pref[r+1] - pref[l]

This makes range sums O(1) after O(n) preprocessing.

Prefix sum + hash map (count subarrays)

For subarray sum = k, you want:

pref[j] - pref[i] = k => pref[i] = pref[j] - k

Scan once and count how many times each prefix sum occurred so far. Initialize with counts[0] = 1 to count subarrays that start at index 0.

Difference arrays (range updates)

If you have many updates [l, r, delta]:

• diff[l] += delta
• diff[r+1] -= delta (if in bounds)

A single prefix sum over diff gives the final array.

Binary search on answer

Use when a predicate is monotonic:

• If X works, then any X' > X also works (or vice versa)

Template for minimum feasible value:

low, high := minPossible, maxPossible
for low < high {
    mid := low + (high-low)/2
    if feasible(mid) {
        high = mid
    } else {
        low = mid + 1
    }
}
return low

For shipping capacity, feasibility is "can ship within D days".

What you will build

• Count subarrays that sum to K.
• Apply range additions with a difference array.
• Find minimum ship capacity with binary search on answer.