Range Sum Query - Immutable
Understand the problem
Given an integer array nums that never changes after initialization, implement a NumArray class that supports many sumRange(left, right) queries — each returns the sum of the elements from index left to right (both ends inclusive).
Example:
const arr = new NumArray([-2, 0, 3, -5, 2, -1])
arr.sumRange(0, 2) // 1 (−2 + 0 + 3)
arr.sumRange(2, 5) // -1 (3 − 5 + 2 − 1)
arr.sumRange(0, 5) // -3The key point: the array is immutable but the number of queries can be huge — the cost of each query is what you need to optimize.
Show the basic approach (slower)
Init O(1) · each query O(n) time, O(1) extra spaceclass NumArrayNaive {
private nums: number[]
constructor(nums: number[]) {
this.nums = nums
}
sumRange(left: number, right: number): number {
// sum the range element by element
let sum = 0
for (let i = left; i <= right; i++) sum += this.nums[i]
return sum
}
}- Every query rescans the whole range.
- With q queries on an array of n elements → O(q·n).
- When q and n are both around 10⁴, that is 10⁸ additions in total — too slow for the time limit.
Optimal solution
Preprocessing O(n) · each query O(1) time, O(n) space for the prefix arrayclass NumArray {
private prefix: number[]
constructor(nums: number[]) {
// prefix[i] = sum of the first i elements; prefix[0] = 0
this.prefix = new Array(nums.length + 1)
this.prefix[0] = 0
for (let i = 0; i < nums.length; i++) {
this.prefix[i + 1] = this.prefix[i] + nums[i]
}
}
sumRange(left: number, right: number): number {
return this.prefix[right + 1] - this.prefix[left]
}
}Pay the cost once, up front: build a prefix array prefix of length n+1 where prefix[i] = the sum of the first i elements.
- The range sum [left, right] =
prefix[right + 1] − prefix[left]— the part of the sum beforeleftappears in both values and cancels out when you subtract, so each query is a single subtraction. - The convention
prefix[0] = 0means queries starting at index 0 need no special case. - This is the classic optimization when the data is immutable and queries are many.
Step-by-step trace
1class NumArray {2 private prefix: number[]3 4 constructor(nums: number[]) {5 // prefix[i] = sum of the first i elements; prefix[0] = 06 this.prefix = new Array(nums.length + 1)7 this.prefix[0] = 08 for (let i = 0; i < nums.length; i++) {9 this.prefix[i + 1] = this.prefix[i] + nums[i]10 }11 }12 13 sumRange(left: number, right: number): number {14 return this.prefix[right + 1] - this.prefix[left]15 }16}Edge cases to remember
Single-element query (left === right): prefix[left+1] − prefix[left] = nums[left] — the formula still holds, no special branch needed.
Whole-array query (0, n−1): prefix[n] − prefix[0] = the total sum, thanks to the anchor prefix[0] = 0.
Array containing negative numbers (as in the example above): the running sum and the subtraction work as usual, and the result can be negative.
One-element array [5]: prefix = [0, 5], sumRange(0, 0) = 5.