#303
Range Sum Query - Immutable
Easy Prefix array
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a class that answers many queries "sum of nums from index left to right" on a fixed array.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: answer "sum from left to right" many times on the same array.
Why this works: build the prefix totals once; every query is then a subtraction.
Example: nums = [-2, 0, 3, -5, 2, -1]
prefix = [0, -2, -2, 1, -4, -2, -3]sum(0..2) = prefix[3] - prefix[0] = 1sum(2..5) = prefix[6] - prefix[2] = -1
✦Hints open one at a time
Summing each range every time is O(n) per query.
Store prefix[i] = sum of the first i elements (prefix[0] = 0).
sum(left..right) = prefix[right + 1] - prefix[left].
↗Approach
Build a prefix array of size n + 1 once in the constructor. Each query is a single subtraction.
</>Solution (Java)
class NumArray {
private final int[] prefix;
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];
}
}!Common mistake
Using a prefix array of size n and then special-casing left = 0. The extra leading 0 removes the edge case.
Complexity
- Time: O(n) to build, O(1) per query.
- Space: O(n).
