Answer many sum(nums[i:j]) range queries on a static array quickly?
Options
- Recompute each sum on demand, O(n) per query
- Prefix sums: each query is
p[j] - p[i](Correct option) - Sort the array once, then slice the range
- Keep a stack of partial sums for each query
Answer
Precompute prefix sums once (O(n)); each query is prefix[j] - prefix[i] (O(1))
Why
Build prefix where prefix[k] is the sum of the first k elements. This takes one pass.
Then the sum of any range i..j-1 is prefix[j] - prefix[i]: one subtraction.
For example nums = [3, 1, 4]: prefix = [0, 3, 4, 8]; sum of nums[1:3] = 8 - 3 = 5.
Remember
Many range sums → prefix sums.