Range Sum Query - Immutable
Easy · Arrays & Hashing · Array · Design · Prefix Sum
Problem
Build a class NumArray that is constructed once from an integer array nums and then answers many range-sum questions about it. The array never changes after construction.
- NumArray(nums) stores whatever it needs from nums.
- sumRange(left, right) returns the sum of nums[left] through nums[right], both ends included.
Because sumRange may be called thousands of times, each query should be fast: ideally constant time after one linear preprocessing step.
The tests describe a run as two lists: ops names each call (the first is the constructor) and args holds each call's arguments. The expected output lists what each call returns, with None for the constructor.
Examples
Input: ops = ["NumArray","sumRange","sumRange","sumRange"], args = [[[4,-1,3,0,2]],[0,2],[1,4],[3,3]] Output: [None, 6, 4, 0]
4 + (-1) + 3 = 6, then -1 + 3 + 0 + 2 = 4, and the single value at index 3 is 0.
Input: ops = ["NumArray","sumRange","sumRange"], args = [[[7,7]],[0,1],[1,1]] Output: [None, 14, 7]
The whole array sums to 14 and the last value alone is 7.
Constraints
- 1 <= len(nums) <= 10^4
- -10^5 <= nums[i] <= 10^5
- 0 <= left <= right < len(nums)
- At most 10^4 calls to sumRange
Approaches
- Baseline: add the range up on every query — time O(1) to build, O(n) per query, space O(n) for the stored copy
Follow-up
What if nums can change between queries? A prefix table would need O(n) work per update. A Fenwick (binary indexed) tree or a segment tree makes both updates and range sums O(log n). The same table also extends to two dimensions, where four lookups answer any rectangle. See the use cases for the reverse trick (many range increments, read back with one running sum) and for the balance point of an array.
Related problems
Start free on Cariara · Coding problems · System design studio
