Prefix Sums & Binary Search on Answer

Earlier boundaries count subarrays

P[j]-P[i]=k → count earlier P[i]=P[j]-k. Initialize count[0]=1; lookup before increment. [2,-2,2,0], k=2 adds 1,0,2,2 → 5.

Signed inputs break simple sum windows

Frequency, not membership: repeated prefixes represent different starts. For k=0, inserting the current prefix before lookup admits empty subarrays.

Difference endpoints

Inclusive [l,r,d]: diff[l]+=d; diff[r+1]-=d. n=5, [1,3,3] and [2,4,-2] → output [0,3,1,1,-2]. A sentinel at n is outside the output.

Binary search needs a proven predicate

Shipping preserves order. Greedy takes the longest fitting prefix each day. Feasible at C implies feasible at every larger C. Bounds: max weight to total weight. Keep mid on success; discard it on failure.

Trace and transfer

[3,2,2,4,1], D=3: capacities 8 yes, 6 yes, 5 yes, 4 no → answer 5. [0,0,0], k=0 has 6 subarrays. Compare small inputs with direct updates, quadratic counting and all contiguous partitions.