core practice · coding problem
Answer range-sum queries in O(1)
Implement makeRangeSum(nums) returning a function query(i, j) that gives the inclusive sum of nums[i..j] in O(1) per call. Build the prefix array once.
The mechanism
A prefix array trades one O(n) pass for O(1) range answers afterwards: sum(i..j) becomes prefix[j+1] - prefix[i]. The generalisation matters more than the trick — any associative, invertible operation works, and the difference array is the same idea run backwards, letting you apply many range updates in O(1) each and materialise the result once.
Expected evidence
const q = makeRangeSum([1,2,3,4,5]); q(1,3) -> 9; q(0,4) -> 15
Try this drill in the practice workspace →
Hints when you need them
- Build prefix of length n+1 so prefix[0] = 0 and you never special-case i === 0.
- Inclusive sum(i..j) is prefix[j+1] - prefix[i].
Watch for these mistakes
- Off-by-one from mixing inclusive and exclusive bounds — fix the convention once and keep it
- Using it for min or max, which are associative but NOT invertible, so subtraction is meaningless (use a sparse table instead)
- Rebuilding the prefix array inside the query loop, which throws away the whole benefit
- Overflow on long integer ranges when the running sum exceeds the element type