EasyEditorial · 6 minGenerated by the editor · Aug 13
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Intuitionwhy one extra prefix entry removes the query loop
A range sum from left to right is the sum of everything from index 0 to right, minus the sum of everything before left. If you store those starting-at-zero sums, the elements before left cancel out and only the requested range remains.
Use a prefix array with length n + 1. Define prefix[i] as the sum of nums[0] through nums[i - 1], so prefix[0] is zero and prefix[i + 1] includes nums[i]. With that definition, the inclusive range is prefix[right + 1] - prefix[left]. The extra entry makes the same formula work when left is zero.
The right endpoint needs right + 1 because the range is inclusive.
Approachbuild once inside the method, then answer by subtraction
1Read n and allocate prefix with n + 1 entries initialized to zero, because prefix[0] represents the sum of an empty prefix and lets the formula handle left = 0.
2Fill prefix from left to right using prefix[i + 1] = prefix[i] + nums[i], because each entry should include one more input value than the entry before it.
3Use right + 1 as the ending prefix position, because prefix[right] stops before nums[right] while the requested range includes it.
4Subtract prefix[left] from prefix[right + 1], because prefix[left] contains exactly the values before the requested range and therefore removes them.
5Return the difference directly, because every value outside the range appears in both prefix sums and cancels.
6Keep the prefix construction before the subtraction, because using an unfilled entry would produce a value that does not represent any input prefix.
Complexitythe query arithmetic is constant time, but this signature rebuilds the table
MEASURE
BOUND
WHY
Time
O(n) per call
The loop creates n prefix relationships, and the final subtraction is O(1). Each input element is processed once, so the work grows with the array length rather than with the width of the requested range.
Space
O(n) extra
The prefix vector stores n + 1 running sums. The returned integer is not additional output storage, and no input shape changes this bound; an array of maximum length still requires a linear prefix table.
Here n is the length of nums. The bounds are for one invocation of sumRange.
CPPBuild the prefix sums and answer the inclusive range with one subtraction.
#include <vector>
using namespace std;
class Solution {
public:
int sumRange(vector<int>& nums, int left, int right) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return prefix[right + 1] - prefix[left];
}
};
The important placement is the index shift in both the construction and the query. Writing nums[i] into prefix[i + 1] reserves prefix[0] for an empty prefix. The query then ends at right + 1, not right, because the prefix position describes values before its index. These two choices are a matched definition; changing only one creates an off-by-one result.
Common mistakestwo index errors that often look plausible