Range Sum Query – Immutable
Problem
Given an array that never changes, answer many queries sumRange(l, r) — the sum of elements from index l to r inclusive — each in O(1).
Example 1
Input: nums = [-2, 0, 3, -5, 2, -1]; sumRange(0,2), sumRange(2,5), sumRange(0,5) Output: 1, -1, -3
Test cases
Case 1
Input: new NumArray([-2,0,3,-5,2,-1]) .sumRange(0, 2) .sumRange(2, 5) .sumRange(0, 5) Expected: [1,-1,-3]
Case 2
Input: new NumArray([1,2,3,4]) .sumRange(1, 1) .sumRange(0, 3) .sumRange(2, 3) Expected: [2,10,7]
Case 3
Input: new NumArray([5]) .sumRange(0, 0) Expected: [5]
View solutionHide solution1 approach
1. Prefix sums
Time O(n) build, O(1) per querySpace O(n)
pre[i] = sum of the first i numbers; sum(l..r) = pre[r+1] − pre[l]. The leading zero removes the l = 0 special case.
class NumArray { constructor(nums) { this.pre = [0]; for (const x of nums) this.pre.push(this.pre[this.pre.length - 1] + x); } sumRange(l, r) { return this.pre[r + 1] - this.pre[l]; }}