264. Range Sum Query - Immutable
Design a class NumArray around a fixed integer array nums that can answer many range-sum questions quickly.
- The constructor receives
nums. The array never changes after construction. sum_range(left, right)returns the sum of the elements from indexleftthrough indexright, both ends included.
Because the same array is queried over and over, do the heavy lifting once in the constructor so each query is cheap.
Example 1:
Input: NumArray([4, -1, 2, 6, -3]); sum_range(1, 3), sum_range(0, 4), sum_range(2, 2)
Output: [7, 8, 2]
Explanation: sum_range(1, 3) adds -1 + 2 + 6 = 7; sum_range(0, 4) is the whole array, 8; sum_range(2, 2) is the single element 2.
Example 2:
Input: NumArray([5]); sum_range(0, 0)
Output: [5]
Explanation: A one-element array: the only possible query returns that element.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁵ ≤ nums[i] ≤ 10⁵
- 0 ≤ left ≤ right < nums.length
- At most 10⁴ calls to sum_range
Hints:
Adding the elements with a loop on every call works, but with many queries you re-add the same numbers thousands of times. What could you compute once, up front, that makes any range sum a couple of lookups?
Precompute running totals: let prefix[i] be the sum of the first i elements (prefix[0] = 0). Then the sum of nums[left..right] is prefix[right + 1] - prefix[left] — one subtraction per query.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: NumArray([4, -1, 2, 6, -3]); sum_range(1, 3), sum_range(0, 4), sum_range(2, 2)
Expected output: [7, 8, 2]