Range Sum Query - Immutable
Description
You get an integer array nums that never changes, and many questions about it.
Implement the class NumArray:
NumArray(nums)gets ready to answer questions aboutnums.sumRange(left, right)returns the sum of the values from indexleftto indexright, both included:nums[left] + nums[left + 1] + ... + nums[right].
Each test builds one NumArray from nums and calls sumRange once for each query, in order; the output is the list of answers.
Examples
Example 1
Input: nums = [-2, 0, 3, -5, 2, -1], queries = [[0, 2], [2, 5], [0, 5]]
Output: [1,-1,-3]
Explanation: -2 + 0 + 3 = 1, 3 - 5 + 2 - 1 = -1, and the whole array adds up to -3.
Example 2
Input: nums = [3, -1, 4, 1, -5, 9], queries = [[2, 5], [0, 2], [3, 3]]
Output: [9,6,1]
Explanation: 4 + 1 - 5 + 9 = 9, 3 - 1 + 4 = 6, and a range of one index is just that value, 1.
Example 3
Input: nums = [7], queries = [[0, 0]]
Output: [7]
Explanation: One value, and the only possible range is that value.
Constraints
- 1 ≤ nums.length ≤ 10^4
- -10^5 ≤ nums[i] ≤ 10^5
- 0 ≤ left ≤ right < nums.length
- At most 10^4 calls are made to sumRange.
Editorial
Brute Force
Intuition
Answer each question the way it's asked: start at 0 and add the values from left to right.
Step-by-Step Explanation
Let's answer sumRange(2, 5) on nums = [-2, 0, 3, -5, 2, -1]:
- Add nums[2] = 3, and the total is 3.
- Add nums[3] = −5, and the total is −2.
- Add nums[4] = 2, and the total is 0.
- Add nums[5] = −1, and the total is −1.
The answer is −1.
Add the Range Up — The shaded cells are the part of the range added so far.
Algorithm
- Keep
nums. - For each
sumRange(left, right): start a total at 0, addnums[left]throughnums[right], and return it.
Code
class NumArray {
vector<int> nums;
public:
NumArray(vector<int>& nums) : nums(nums) {}
int sumRange(int left, int right) {
int total = 0;
for (int i = left; i <= right; i++) // add the range up, every call
total += nums[i];
return total;
}
};
class NumArray:
def __init__(self, nums: list[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
total = 0
for i in range(left, right + 1): # add the range up, every call
total += self.nums[i]
return total
class NumArray {
private final int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int left, int right) {
int total = 0;
for (int i = left; i <= right; i++) // add the range up, every call
total += nums[i];
return total;
}
}
var NumArray = function(nums) {
this.nums = nums;
};
NumArray.prototype.sumRange = function(left, right) {
let total = 0;
for (let i = left; i <= right; i++) // add the range up, every call
total += this.nums[i];
return total;
};
Complexity Analysis
Time Complexity: O(n) per call
A call can cover the whole array, so q calls cost O(n · q).
Space Complexity: O(1) beyond the array.
Why This Approach Is Not Efficient
With 10^4 values and 10^4 calls that each cover the whole array, that's 10^8 additions (over the time limit in Python).
And the calls repeat each other's work: two overlapping ranges add the same values twice. The array never changes, so do the adding once, up front, and keep the results.
Optimal Approach - Prefix Sums
Intuition
Keep the running totals: prefix[i] is the sum of the first i values, with prefix[0] = 0. Then prefix[right + 1] is everything up to and including nums[right], and prefix[left] is everything before nums[left]. Every value before left is in both, so it cancels:
sumRange(left, right) = prefix[right + 1] − prefix[left]
Picture each total standing on the gap just before its value: the answer is the total on the gap after right minus the total on the gap before left. The 0 in front is the gap before everything, which is why a range starting at 0 needs no special case.
Step-by-Step Explanation
Let's build the totals for nums = [-2, 0, 3, -5, 2, -1], then answer sumRange(0, 2), sumRange(2, 5), sumRange(0, 5):
- prefix[1] = prefix[0] + nums[0] = 0 − 2 = −2.
- prefix[2] = prefix[1] + nums[1] = −2 + 0 = −2.
- prefix[3] = prefix[2] + nums[2] = −2 + 3 = 1.
- prefix[4] = prefix[3] + nums[3] = 1 − 5 = −4.
- prefix[5] = prefix[4] + nums[4] = −4 + 2 = −2.
- prefix[6] = prefix[5] + nums[5] = −2 − 1 = −3.
- sumRange(0, 2) is prefix[3] − prefix[0] = 1 − 0 = 1: one subtraction.
- sumRange(2, 5) is prefix[6] − prefix[2] = −3 − (−2) = −1: one subtraction.
- sumRange(0, 5) is prefix[6] − prefix[0] = −3 − 0 = −3: one subtraction.
The answers are [1, -1, -3].
Build the Running Totals, Then Subtract — Top: nums. Bottom: the running totals, each under the gap before its value.
Algorithm
- Make
prefixwith n + 1 slots,prefix[0] = 0. - For each i,
prefix[i + 1] = prefix[i] + nums[i]. - For each
sumRange(left, right), returnprefix[right + 1] − prefix[left].
Code
class NumArray {
vector<int> prefix; // prefix[i] = nums[0] + ... + nums[i - 1]; at most 10^9 in size
public:
NumArray(vector<int>& nums) : prefix(nums.size() + 1, 0) {
for (size_t i = 0; i < nums.size(); i++)
prefix[i + 1] = prefix[i] + nums[i];
}
int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left]; // the total after right minus the total before left
}
};
class NumArray:
def __init__(self, nums: list[int]):
self.prefix = [0] * (len(nums) + 1) # prefix[i] = nums[0] + ... + nums[i - 1]; prefix[0] = 0
for i, x in enumerate(nums):
self.prefix[i + 1] = self.prefix[i] + x
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left] # the total after right minus the total before left
class NumArray {
private final int[] prefix; // prefix[i] = nums[0] + ... + nums[i - 1]; at most 10^9 in size
public NumArray(int[] nums) {
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++)
prefix[i + 1] = prefix[i] + nums[i];
}
public int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left]; // the total after right minus the total before left
}
}
var NumArray = function(nums) {
this.prefix = new Array(nums.length + 1).fill(0); // prefix[i] = nums[0] + ... + nums[i - 1]; prefix[0] = 0
for (let i = 0; i < nums.length; i++)
this.prefix[i + 1] = this.prefix[i] + nums[i];
};
NumArray.prototype.sumRange = function(left, right) {
return this.prefix[right + 1] - this.prefix[left]; // the total after right minus the total before left
};
Complexity Analysis
Time Complexity: O(n) to build, O(1) per call
q calls cost O(n + q) in all.
Space Complexity: O(n) for the n + 1 totals.
The totals stay within 10^4 · 10^5 = 10^9 in size here, so a 32-bit int holds them; with bigger limits, use long.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Leaving out the zero in front. return self.prefix[right] - self.prefix[left - 1]
On nums = [4, -2, 7, 1, 9] with sumRange(0, 2), it returns [-10]; the answer is [9]. With prefix[i] = nums[0] + ... + nums[i], a range is prefix[right] - prefix[left - 1], and a range that starts at 0 asks for prefix[-1]. Python reads that as the last total, the sum of the whole array, and returns a wrong number with no error. A 0 in front (prefix[0] = 0) makes every range one subtraction, including the ones that start at 0.
Subtracting the total after left. return self.prefix[right + 1] - self.prefix[left + 1]
On nums = [4, -2, 7, 1, 9] with sumRange(1, 3), it returns [8]; the answer is [6]. prefix[left + 1] is the total up to and including nums[left], so subtracting it removes nums[left] from the range. The total before left is prefix[left].
Stopping before right. return self.prefix[right] - self.prefix[left]
On nums = [4, -2, 7, 1, 9] with sumRange(1, 3), it returns [5]; the answer is [6]. prefix[right] stops just before nums[right], so the range loses its last value. The total after right is prefix[right + 1].
Where This Pattern Is Taught
This problem practises range sums from running totals. It's taught in Introduction to Prefix Sums.