Range Sum Query - Immutable
Problem
NumArray that is built once from an integer array
nums (which never changes afterwards) and then answers many queries
sumRange(left, right): the sum of nums[left..right], both ends
inclusive.[-2,0,3,-5,2,-1], (0,2)Output1same array, (2,5)Output-1same array, (0,5)Output-31 ≤ n ≤ 104 · -105 ≤ nums[i] ≤ 105 · 0 ≤ left ≤ right < n · up to 104 queries
Try it yourself
class NumArray {
public NumArray(int[] nums) {
}
public int sumRange(int left, int right) {
}
}
prefix[i] = sum of the first i elements, any range sum is just
prefix[right+1] - prefix[left].Instinct Repeated range-sum queries, or "count subarrays whose sum equals / divides K" with negatives allowed? Store running totals and subtract two of them.
Memory hack Any range is two prefixes apart - sum(i..j) = P[j+1] - P[i], so remember every P you've passed.
Open the Prefix Sum guide →Approaches
Brute ForceLoop Over the Range per Query
O(1) init · O(n)/querySpace O(1) extraKeep a reference to nums and, on every query, add up
nums[left] through nums[right]. Nothing is reused
between queries.
class NumArray { private int[] nums; public NumArray(int[] nums) { this.nums = nums; } public int sumRange(int left, int right) { int sum = 0; for (int k = left; k <= right; k++) sum += nums[k]; return sum; } }
Trivial, but q queries cost O(q · n) — up to 108 steps.
BetterPrecompute Every Range (2-D Cache)
O(n2) init · O(1)/querySpace O(n2)Since the data never changes, answer every possible query in advance:
for each start i, extend a running sum to every end j
and store it in sums[i][j]. A query becomes a table lookup.
class NumArray { private int[][] sums; public NumArray(int[] nums) { int n = nums.length; sums = new int[n][n]; for (int i = 0; i < n; i++) { int run = 0; for (int j = i; j < n; j++) { run += nums[j]; sums[i][j] = run; } } } public int sumRange(int left, int right) { return sums[left][right]; } }
O(1) queries, but n = 104 needs 108 cells (~400 MB) — impractical.
OptimalPrefix Sum Array
O(n) init · O(1)/querySpace O(n)Store only n+1 numbers: prefix[i+1] = prefix[i] +
nums[i]. The sum of [left..right] is “everything up to
right” minus “everything before left”.
The leading 0 removes the left == 0 special case.
class NumArray { private int[] prefix; // prefix[i] = nums[0] + ... + nums[i-1] 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]; } }
Dry runprefix of [-2,0,3,-5,2,-1]
- build0-2-21-4-2-3prefix[i+1]=prefix[i]+nums[i]
- (0,2)0L-2-21R-4-2-31 - 0 = 1
- (2,5)0-2-2L1-4-2-3R-3 - (-2) = -1
- (0,5)0L-2-21-4-2-3R-3 - 0 = -3 ✔
Linear preprocessing, constant-time queries, linear memory — the best of both.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Loop Over the Range per Query | O(1) init · O(n)/query | O(1) extra |
| Better | Precompute Every Range (2-D Cache) | O(n2) init · O(1)/query | O(n2) |
| Optimal | Prefix Sum Array | O(n) init · O(1)/query | O(n) |
- Off-by-one: with a size-
n+1array useprefix[right+1] - prefix[left]. - Size-
nprefix without the leading 0 → needs a special case forleft == 0. - Recomputing sums inside
sumRange— defeats the purpose of the design.
- Ask how many queries vs. updates: immutable data favours heavy preprocessing.
- Explain the space/time trade-off between the 2-D cache and the prefix array.
- Mention the mutable follow-up (LC 307) needs a Fenwick or segment tree.