Range Sum Query – Immutable

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}
}