Range Sum Query - Immutable
Easy· prefix array· design
Problem
Design a class that is built once from an integer array and then answers many queries of the form sumRange(left, right), the sum of elements from index left to right inclusive. The array never changes after construction.
Examples
Input: nums = [-2,0,3,-5,2,-1]; sumRange(0,2), sumRange(2,5), sumRange(0,5)
Output: 1, -1, -3
For instance sumRange(2,5) = 3 + (-5) + 2 + (-1) = -1.
Constraints
- • 1 <= nums.length <= 10^4
- • 0 <= left <= right < nums.length
- • Up to 10^4 queries
Hints & approach
Hint 1
Summing each range on demand is O(n) per query. Can you pay that cost once?
Hint 2
Store prefix[i] = sum of the first i elements.
Approachtry the hints first
In the constructor, build an array prefix of length n + 1 where prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i]. The sum of nums[left..right] is then prefix[right + 1] - prefix[left]. The extra leading zero removes the special case for left = 0. Construction is O(n) and each query is O(1).
Time O(n) build, O(1) per query · Space O(n)