Why it works
- prefix[j] is the sum of the first j numbers. The numbers from left to right are the first right + 1 numbers without the first left ones, so their sum is prefix[right + 1] − prefix[left].
- The extra slot prefix[0] = 0 is the sum of no numbers: a query from index 0 subtracts it and needs no special case.
- The array never changes, so the table built once stays right for every query, and each query is two lookups however long its range is.
Complexity
init: time O(n) and memory O(n) for n + 1 sums. Each sumRange: time O(1), two lookups and a subtraction.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗