Range Sum Query - Immutable
Problem
Design a data structure that supports repeated sumRange(l, r) queries returning sum(nums[l..r]) for an immutable array nums.
nums = [-2,0,3,-5,2,-1]; sumRange(2,5)-1class NumArray:
def __init__(self, nums):
self.pref = [0]
for x in nums:
self.pref.append(self.pref[-1] + x)
def sumRange(self, l, r):
return self.pref[r + 1] - self.pref[l]class NumArray {
constructor(nums) {
this.pref = [0];
for (const x of nums) this.pref.push(this.pref[this.pref.length - 1] + x);
}
sumRange(l, r) { return this.pref[r + 1] - this.pref[l]; }
}class NumArray {
int[] pref;
public NumArray(int[] nums) {
pref = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) pref[i + 1] = pref[i] + nums[i];
}
public int sumRange(int l, int r) { return pref[r + 1] - pref[l]; }
}class NumArray {
vector pref;
public:
NumArray(vector& nums) {
pref.resize(nums.size() + 1, 0);
for (int i = 0; i < (int)nums.size(); i++) pref[i + 1] = pref[i] + nums[i];
}
int sumRange(int l, int r) { return pref[r + 1] - pref[l]; }
}; Explanation
Since the array never changes but we get many sum queries, we do the heavy work once up front. We build a prefix-sum array pref where pref[i] is the sum of the first i numbers, and then every query is a single subtraction.
The build is simple: start pref with a 0 and keep pushing pref[-1] + x for each value x. So pref grows one longer than nums, with pref[i] holding the running total up to (but not including) index i.
To answer sumRange(l, r) we return pref[r+1] - pref[l]. The big prefix up to r minus the prefix just before l leaves exactly the chunk from l to r.
Example: nums = [-2,0,3,-5,2,-1] gives pref = [0,-2,-2,1,-4,-2,-3]. Then sumRange(2,5) = pref[6] - pref[2] = -3 - (-2) = -1, matching the direct sum of 3 + (-5) + 2 + (-1).
Building is O(n) once and each query is O(1), which is a huge win when there are lots of queries.