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.
The key idea in this approach is to use a prefix sum array. We precompute cumulative sums such that each element at index i in this prefix array contains the sum of all elements in the nums array from index 0 to i. The sum of a subarray can then be computed in constant time using the relation: sumRange(left, right) = prefixSum[right] - prefixSum[left-1]. This pre-computation allows each query to be answered in O(1) time after O(n) pre-computation.
This C solution defines a structure NumArray that contains the prefix sums array. In the numArrayCreate function, we allocate memory for the prefix sums and fill it such that each entry in the array contains the cumulative sum up to that index. The numArraySumRange function then computes the sum of any given range using precomputed values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for precomputing the prefix sums, O(1) for each range query.
Space Complexity: O(n) for storing the prefix sums.
A Segment Tree is a data structure that allows efficient range query and update operations. It is particularly useful in scenarios where there are multiple queries of the dynamic array that could change over time. For sumRange queries, the segment tree helps to retrieve the sum in logarithmic time, and it can be further extended to handle updates if needed.
This C solution involves a Segment Tree built in a bottom-up manner. The buildTree function constructs the tree. During a sumRange query, the results from relevant nodes are combined. numArrayFree is used to clean resources.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for building the tree, O(log n) per query.
Space Complexity: O(n) for the segment tree.
| Approach | Complexity |
|---|---|
| Prefix Sum Array | Time Complexity: O(n) for precomputing the prefix sums, O(1) for each range query. |
| Segment Tree | Time Complexity: O(n) for building the tree, O(log n) per query. |
| 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 |
Range Sum Query 2D - Immutable - Leetcode 304 - Python • NeetCode • 50,535 views views
Watch 9 more video solutions →Practice Range Sum Query - Immutable with our built-in code editor and test cases.
Practice on FleetCode