Range Sum Query - Immutable
Last Updated: April 3, 2026
Understanding the Problem
We need to build a data structure that preprocesses an integer array so we can quickly answer range sum queries. Each query gives us two indices, left and right, and asks for the sum of all elements between those positions (inclusive).
The critical detail here is that the array is immutable, meaning it never changes after construction. This is great news because it means we can precompute whatever we want during initialization and reuse it across all queries. The question is: what should we precompute to make each query as fast as possible?
Key Constraints:
nums.length <= 10^4→ The array is small enough that even O(n) preprocessing is trivial.At most 10^4 calls to sumRange→ If each query is O(n), total work is O(n * q) = O(10^8), which is borderline. O(1) per query would be much safer.nums[i]can be negative → We can't make assumptions about sums being monotonically increasing. Simple prefix comparisons won't help with pruning.left <= right→ We don't need to handle invalid ranges where left > right.
Approach 1: Brute Force
Intuition
The simplest approach is to do exactly what the problem says: for each sumRange call, loop from left to right and add up the elements. No preprocessing needed, and it's easy to implement.
This works fine for a small number of queries, but it does redundant work. If you query sumRange(0, 5) and then sumRange(0, 3), the second query re-adds elements you already summed in the first one. Every query starts from scratch.
Algorithm
- Store the input array as-is during construction.
- For each
sumRange(left, right)call, initialize a running sum to 0. - Loop from index
lefttoright, adding each element to the running sum. - Return the running sum.
Example Walkthrough
Code
- Time Complexity: O(n) per query, where n is the length of the array. In the worst case, we iterate through every element. With q queries, total time is O(n * q).
- Space Complexity: O(n) for storing the array. We just keep a reference to the original array with no additional data structures.
This approach works but every query loops through the range from scratch. Since the array never changes, what if we precomputed cumulative sums once and used subtraction to answer any query in O(1)?
Approach 2: Prefix Sum
Intuition
Here's the key insight: if you know the sum of elements from index 0 to any index k, you can compute the sum of any subarray using simple subtraction.
Let's define prefix[i] as the sum of all elements from index 0 to index i - 1. Then:
sum(left, right) = prefix[right + 1] - prefix[left]
prefix[right + 1] gives us the sum of elements from 0 to right. But we don't want elements 0 through left - 1. So we subtract prefix[left], which is exactly that unwanted portion. What remains is the sum from left to right.
We build this prefix array once during construction, and every query becomes a single subtraction.
The prefix sum technique leverages a property of addition: any contiguous subarray sum can be expressed as the difference of two prefix sums. If prefix[k] represents the sum of the first k elements, then the sum of elements from index left to right is prefix[right + 1] - prefix[left]. This transforms a range query (which normally requires iteration) into constant-time arithmetic.
The reason we use an array of size n + 1 with prefix[0] = 0 is to handle the edge case where left = 0 cleanly. Without this padding, we'd need a special case: "if left is 0, return prefix[right]; otherwise return prefix[right] - prefix[left - 1]." The extra element at the start eliminates that branch entirely.
Algorithm
- Create a
prefixarray of sizen + 1, wherenis the length ofnums. - Set
prefix[0] = 0(sum of zero elements). - For each index
ifrom 0 to n - 1, setprefix[i + 1] = prefix[i] + nums[i]. - For each
sumRange(left, right)call, returnprefix[right + 1] - prefix[left].
Example Walkthrough
Code
- Time Complexity: O(n) for construction, O(1) per query. Building the prefix array requires one pass through the input. After that, every sumRange call is a single subtraction.
- Space Complexity: O(n) for the prefix array. We store one extra element per input element, plus one padding element at index 0.