Prefix Sums & Binary Search on Answer

The exercises count exact-sum subarrays, batch inclusive range additions and minimize shipping capacity. Prepare by tracing half-open array slices and a frequency map. These techniques all remove repeated work, but they rely on different invariants; choose one by the contract rather than by keywords.

Count earlier boundaries, not earlier values

Let P[0]=0 and P[j] be the sum of the first j elements. The nonempty slice nums[i:j] sums to P[j]-P[i]. To get target k at boundary j, count earlier boundaries with P[i]=P[j]-k. Store frequencies, because repeated prefix sums represent distinct starting positions.

For [2,-2,2,0], k=2, start with counts={0:1}:

New boundary j	New P[j]	Earlier count of P[j]-2	Added	Total
1	2	count[0]=1	1	1
2	0	count[-2]=0	0	1
3	2	count[0]=2	2	3
4	2	count[0]=2	2	5

After each lookup, increment counts[P[j]]. Reversing that order admits i=j; for k=0 this counts an empty subarray at every step. Omitting initial 0:1 loses slices beginning at index 0. A set also fails because it collapses distinct boundaries with the same sum.

Unlike the positive-only minimum-length window, this works with negative values. On [3,-2,2], target 3, shrinking immediately after seeing 3 would lose the full-array match later. A signed sum does not monotonically grow when the right endpoint moves. SubarraySumK takes O(n) expected time with a hash map and O(n) space. Prefix sums and the count can exceed 32-bit range under this exercise's limits; use the course's 64-bit Go environment or wide internal arithmetic and a representable output.

Range updates change where an effect begins and ends

RangeAddition(n, updates) starts from zeros; [l,r,d] includes both endpoints. Instead of touching every cell, record diff[l]+=d and diff[r+1]-=d when that second cell is represented. A prefix scan carries the effect between endpoints. An n+1 buffer may hold the cancellation at n; it is not part of the output.

For n=5, add 3 to [1,3] and -2 to [2,4]:

After first update:  diff = [0, 3,  0, 0,-3, 0]
After second:        diff = [0, 3, -2, 0,-3, 2]
Prefix output:              [0, 3,  1, 1,-2]

A cancellation at r rather than r+1 drops the final included cell. Updates commute because their contributions add; the algorithm costs O(n+u), where u is update count. This is a batch algorithm. To answer interleaved updates and queries, revisit Fenwick or segment trees rather than repeatedly rebuilding.

Search capacity only after proving the feasibility test

MinShipCapacity(weights, days) preserves package order and ships within, not necessarily in exactly, days. All weights are positive. A capacity below the largest package is impossible; the total weight is feasible in one day.

For a fixed capacity, greedily load the longest fitting prefix each day. No other valid first day can ship more packages. Applying that argument to every remaining suffix shows this simulation uses the minimum possible days. If it fits in D days at capacity C, the same grouping also fits at every C'>C. Thus the predicate is false, false, ..., true, true; there is one boundary to find.

For [3,2,2,4,1] and D=3, start [low,high]=[4,12]:

Mid	Greedy daily groups	Feasible?	New bounds
8	[3,2,2] / [4,1]	yes	[4,8]
6	[3,2] / [2,4] / [1]	yes	[4,6]
5	[3,2] / [2] / [4,1]	yes	[4,5]
4	[3] / [2,2] / [4] / [1]	no	[5,5]

Answer 5. Maintain “the optimum lies in the inclusive interval [low,high]”. On success keep mid with high=mid; on failure discard it with low=mid+1. Using high=mid-1 with this loop can discard the optimum. Sorting the weights changes the problem. Compute mid=low+(high-low)/2; bounds and running loads must also fit the numeric type. Complexity is O(n * (1 + log(S-M+1))), with S the sum and M the largest weight. The initial bound scan costs O(n), including the singleton search domain S=M; each predicate simulation also costs O(n).

Finish the missing state

1. For [0,0,0], k=0, two elements have been processed: total=3 and count[0]=3. What is the final total, and why does a boolean “seen zero” fail?
2. For n=4, updates [0,3,5] and [1,1,-2], write a difference array with a sentinel and its four-element output.
3. For [4,1,3,2], D=2, capacity 5 works. Show why capacity 4 fails. Then change D to 4 and predict the result without running binary search.

Check your reconstruction

1. Add 3, then increment the frequency: total 6. There are three distinct earlier zero boundaries for the third end, not just one.
2. Difference [5,-2,2,0,-5], output [5,3,5,5].
3. At capacity 4, groups are [4] / [1,3] / [2], needing three days. For D=4, capacity 4 is enough and no capacity below the largest package is possible.

Implement all three contracts, then compare small signed arrays against a quadratic subarray counter, range updates against direct additions and shipping against exhaustive contiguous partitions. On a later revisit, explain why the first exercise permits negative values while the third's monotonic simulation relies on its stated positive-weight domain.