Range Sum Query - Immutable
Problem Statement
Design a class NumArray that is initialized with an integer array nums and supports sumRange(left, right), which returns the sum of elements from index left through index right inclusive.
Input
A constructor call NumArray(nums) followed by zero or more sumRange(left, right) queries.
Output
For each query, return the integer sum of nums[left] through nums[right].
Constraints
- •
1 <= nums.length <= 10^4 - •
-10^5 <= nums[i] <= 10^5 - •
0 <= left <= right < nums.length - •
At most 10^4 calls will be made to sumRange
Examples
Example 1
nums = [-2,0,3,-5,2,-1], queries = sumRange(0,2), sumRange(2,5), sumRange(0,5)
1, -1, -3Example 2
nums = [5], queries = sumRange(0,0)
5Learning Objectives
- Recognise many immutable range-sum queries as a prefix-sum preprocessing problem.
- Use a leading zero in **prefix** to make inclusive ranges easy to subtract.
- Separate constructor preprocessing cost from O(1) query cost.
- Explain why immutability makes preprocessing especially powerful.
Intuition
Pattern Recognition
This is a prefix-sum design problem because the same array is queried many times and the array never changes. The tempting query implementation loops from left to right every time, which is acceptable for one query but wasteful for thousands.
Precompute a prefix array where prefix[i] stores the sum of the first i numbers. Then every inclusive range can be answered by subtracting the total before the range from the total through the range. The leading 0 at prefix[0] removes special cases for ranges that start at index 0.
Common mistakes
- ×Building **prefix** with the same length as **nums** and then writing extra edge cases for **left = 0**.
- ×Using **prefix[right] - prefix[left]** and accidentally excluding **nums[right]**.
- ×Recomputing the range sum inside every query even though the array is immutable.
- ×Forgetting that negative numbers are fine because subtraction of prefix totals still works.
Algorithm Explanation
Key idea
Build prefix with length n + 1, where prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i]. The sum from left through right is the total through right minus the total before left, so sumRange(left, right) = prefix[right + 1] - prefix[left].
Walkthrough
For nums = [-2,0,3,-5,2,-1], the prefix array becomes [0,-2,-2,1,-4,-2,-3]. To answer sumRange(2,5), take prefix[6] - prefix[2] = -3 - -2 = -1. This subtracts away everything before index 2 and leaves exactly 3,-5,2,-1.
Algorithm
- In the constructor, allocate prefix with one extra slot.
- Set prefix[0] = 0 as the empty prefix before the array begins.
- For each index i, store prefix[i + 1] = prefix[i] + nums[i].
- For sumRange(left, right), return prefix[right + 1] - prefix[left].
- Do not modify prefix during queries because the original array is immutable.
Solutions
Solution: Precomputed prefix array
Pay O(n) once in the constructor to build a prefix array with a leading zero. Each range query then becomes one subtraction between two prefix totals.
Step-by-step
- Allocate prefix with nums.length + 1 entries.
- Fill prefix[index + 1] from left to right using the previous prefix total.
- For a query, read the prefix after right and subtract the prefix before left.
- Return the difference as the inclusive range sum.
O(n) constructor, O(1) per query
O(n)
The extra prefix array stores one running total for every boundary between elements.
Java implementation
Dry Run
Sample input
nums = [-2,0,3,-5,2,-1]. Build prefix, then answer sumRange(2,5).
| step | index or query | prefix value | formula or range | answer |
|---|---|---|---|---|
| build | 0 | prefix[1] = -2 | 0 + -2 | not queried |
| build | 1 | prefix[2] = -2 | -2 + 0 | not queried |
| build | 2 | prefix[3] = 1 | -2 + 3 | not queried |
| build | 3 | prefix[4] = -4 | 1 + -5 | not queried |
| build | 4 | prefix[5] = -2 | -4 + 2 | not queried |
| build | 5 | prefix[6] = -3 | -2 + -1 | not queried |
| query | left = 2, right = 5 | prefix[6] and prefix[2] | -3 - -2 | -1 |
The prefix array stores sums at boundaries, so subtracting boundary 2 from boundary 6 isolates indices 2 through 5.
Interview Tips
Present this as a tradeoff: O(n) preprocessing buys O(1) queries because the array is immutable. Emphasize the extra leading zero because it is the detail that removes off-by-one edge cases. If the interviewer asks about updates, this exact structure no longer works efficiently and you can discuss Binary Indexed Trees or Segment Trees.
Likely follow-ups
- How would the design change if **nums[index]** could be updated after construction?
- How would you support range-sum queries on a 2D matrix?
- What if the query asked for the average instead of the sum?
- When would you choose a Segment Tree over a prefix array?
Similar Problems
Key Takeaways
- A leading zero makes **prefix[right + 1] - prefix[left]** work for every inclusive range.
- Immutable arrays are ideal for preprocessing because query work can be moved to construction.
- Prefix sums answer range sums by subtracting away everything before the range.
- Updates break the static-prefix assumption and call for different data structures.