Watch 10 video solutions for Range Sum Query - Immutable, a easy level problem involving Array, Design, Prefix Sum. This walkthrough by NeetCode has 50,535 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums, handle multiple queries of the following type:
nums between indices left and right inclusive where left <= right.Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums.int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3] Explanation NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 1050 <= left <= right < nums.length104 calls will be made to sumRange.Problem Overview: You receive an integer array and must answer multiple queries asking for the sum of elements between two indices left and right (inclusive). The array never changes after initialization, so the challenge is designing a structure that answers range sum queries efficiently.
Approach 1: Brute Force Iteration (O(n) per query, O(1) space)
The simplest method recomputes the sum for every query. Iterate from index left to right and accumulate the values. Each query scans a portion of the array, so the time complexity is O(n) in the worst case per query. This approach requires no preprocessing and only constant extra space, but performance quickly degrades when many queries are executed. It mainly serves as a baseline that demonstrates why preprocessing is useful.
Approach 2: Prefix Sum Array (O(n) preprocessing, O(1) query, O(n) space)
The optimal solution precomputes cumulative sums using a prefix sum array. During initialization, build an array where prefix[i] stores the sum of elements from index 0 through i. Once built, any query can be answered using subtraction: sum(left, right) = prefix[right] - prefix[left - 1] (with a small edge-case check when left = 0). Preprocessing runs once in O(n), and every query becomes a constant-time lookup. This works well because the underlying array never changes.
Approach 3: Segment Tree (O(n) build, O(log n) query, O(n) space)
A segment tree stores range sums in a balanced tree structure where each node represents the sum of a segment of the array. Queries traverse only the nodes that overlap with the requested range, producing a time complexity of O(log n). This structure is powerful when the array supports updates because modifications can also be handled in O(log n). In this specific problem the array is immutable, so the segment tree is more complex than necessary compared to prefix sums.
Recommended for interviews: Prefix sum is the expected solution. Interviewers want to see that you recognize the array never changes and trade a one-time preprocessing step for constant-time queries. Mentioning the brute force approach first shows you understand the baseline, while implementing prefix sums demonstrates algorithmic optimization and familiarity with a common pattern used in many range query problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n) per query | O(1) | Small input sizes or very few queries |
| Prefix Sum Array | O(n) build, O(1) query | O(n) | Best choice when the array is immutable and queries are frequent |
| Segment Tree | O(n) build, O(log n) query | O(n) | Useful if range queries and updates both need to be supported |