29. Range Sum Query — Immutable
Construct an object that captures the initial array values and answers repeated sum queries efficiently. A query includes the left boundary and excludes the right boundary.
Later changes to the caller's original array must not change the captured data. Empty ranges and boundary validation follow the precise contract below.
Example 1
Input
nums=[2,-1,3]; sumRange(1,3)
Output
2
Explanation: The half-open range includes -1 and 3, but excludes index 3.
Example 2
Input
nums=[2,-1,3]; sumRange(2,2)
Output
0
Explanation: Equal boundaries select no elements.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= left <= right <= nums.length- Queries use a half-open range [left, right). Construction saves a snapshot of the values.
Hints
Hint 1
Define the sum before each boundary, including zero.
Hint 2
How do two prefixes cancel the positions before left?
Hint 3
Store n+1 long prefixes and return prefix[right]-prefix[left].
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Build once, query several boundary pairs
[2,-1,3]
[[0,3],[1,3],[2,2]]
[4,2,0]