Range Sum Query - Immutable
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
