Decide window versus prefix sums
Updated
Window when the constraint is monotonic in L for a fixed R: adding a left cell cannot help once you already shrunk past it (positives and sums ≤/≥, products, counts, distinct). Prefix+hash when you need an exact range sum, especially with negatives.
What to focus on
Range-sum queries and subarray-sum-equals-k (with negatives) are prefix. Longest sum ≤ k on non-negatives is a window. Product < limit is a window. Prefix products do not subtract.
Worked examples
window sum ≤ 10
a = [4, 1, 9, 1], all positive- [0,2] 14 too big → L++
- dropping left is safe
Result: window
prefix sum == 10
a = [4, 1, 9, 1], count slices summing to 10- 1+9 and 9+1
- hash previous prefix values
Result: prefix + hash, not shrink
window product
a = [1, 2, 3, 4], prod < 10- divide to undo a left factor
- no prefix difference for *
Result: window
Try it
Write classifySum(a). a is an array of integers. Window when dropping left is safe (positives, sums ≤/≥, products). Prefix+hash for exact range sum, especially with negatives. Print window or prefix for each job. Return nothing. Longest sum ≤ 10 on [4, 1, 9, 1], count sum==10 on [4, 1, 9, 1], prod<10 on [1, 2, 3, 4], and range-sum queries.
Window-sum cases use positive integers. Exact-sum and range-sum may include any integers.