Range Sum Query — Immutable
Module 12 · Prefix Sum
Problem
Given an integer array nums, implement NumArray supporting
sumRange(left, right) — the sum of nums[left..right] inclusive — for
many calls. The array never changes between calls.
Examples
Example 1
Input
NumArray([-2, 0, 3, -5, 2, -1]), sumRange(0, 2)Output1Explanation. -2+0+3
Example 2
Input
sumRange(2, 5)Output-1Explanation. 3-5+2-1
Example 3
Input
sumRange(0, 5)Output-3Explanation. -2+0+3-5+2-1
Constraints
1 ≤ n ≤ 10⁴ · up to 3·10⁴ calls to
sumRange.
Attempt it first
This problem exists to make the basics lesson's trade concrete: it's literally "build the object once, answer queries fast," phrased as a class. The whole exercise is placing the O(n) work in the constructor and the O(1) work in the query — get that placement backwards and the solution technically works but fails the reason the problem exists.