Range Sum Query - Immutable

Problem

You are given an integer array and will be asked many range queries. Build a data structure that can return the sum of the elements between indices l and r (inclusive) for each query.

Example 1:

Input: nums = [3, 1, 4, 2], queries = [[1, 2], [0, 3], [2, 2]]
Output: [5, 10, 4]
Explanation: sum(1, 2) = 1 + 4 = 5; sum(0, 3) = 3 + 1 + 4 + 2 = 10; sum(2, 2) = 4.

Example 2:

Input: nums = [-2, 5, -1], queries = [[0, 2], [1, 1]]
Output: [2, 5]
Explanation: sum(0, 2) = -2 + 5 - 1 = 2; sum(1, 1) = 5.

Example 3:

Input: nums = [6], queries = [[0, 0]]
Output: [6]

Constraints:

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• 1 <= number of queries <= 10^4
• The array does not change between queries.

Solution Breakdown

Approach - precompute a prefix sum array once, then answer every query with two array reads.

The brute force sums each range on demand: O(n) per query and O(n x q) overall - 10^8 operations at the constraint ceilings, past the time budget. The observation that kills the brute force is that ranges overlap: consecutive queries re-add the same elements. Hoist that repeated work into one O(n) precomputation.

Build an array of length n+1 where prefix[i+1] holds the sum of the first i+1 elements, with prefix[0] = 0 as the empty-prefix base. The recurrence prefix[i+1] = prefix[i] + nums[i] fills it in one pass. Then the sum of nums[l..r] is prefix[r+1] - prefix[l]: the subtrahend is exactly the total of everything before index l, so the difference retains precisely the window and nothing else. The length n+1 (not n) is what removes the special cases - l = 0 subtracts prefix[0] = 0, and r = n-1 reads prefix[n], which exists.

Edge cases - a single-element window sum(l, l) degenerates to prefix[l+1] - prefix[l] = nums[l], correct by the build recurrence. Negative values need no special handling; prefix sums are pure arithmetic, not a monotone structure.

Complexity - O(n) build plus O(1) per query, O(n + q) total; O(n) auxiliary space for the prefix array. The trade is space for query speed, and it holds only because the array is immutable - a single mutation invalidates every prefix from that point forward.