The problem
Given a fixed integer array, answer many sumRange(left, right) queries — the sum of elements between the two indices inclusive.
Stuck? Reveal hints one at a time
How to approach it
- 1Build prefix of length n + 1 with prefix[0] = 0 and prefix[i+1] = prefix[i] + nums[i].
- 2sumRange(l, r) = prefix[r + 1] − prefix[l].
Key insight
The length-(n+1) prefix with a leading zero removes every edge case — sumRange(0, r) needs no special branch.
The solution
Watch out for
- Off-by-one: the subtrahend is prefix[left], not prefix[left + 1].
- If updates arrive later, this design collapses — that is the mutable variant (Fenwick tree).