Problem Statement
Range Sum Query - Immutable
You are given a list of numbers that never changes. People keep asking you, "What do all the numbers from position left to position right add up to?" You might get asked this many times. The slow way is to add up that stretch of numbers fresh every single time. The fast way uses a prefix sum. A prefix sum is a running total: you walk through the list once and write down, at each spot, the sum of everything up to that point. Think of it like a bank statement where each line shows your balance so far, not just that day's change. Once you have those running totals, the sum of any stretch is just one subtraction: the balance at the end minus the balance right before the start. Here we build an array called prefix where prefix[i] holds the sum of nums[0..i-1], so the answer to sum(left, right) is prefix[right+1] - prefix[left].
Signals to notice
Brute force first
Sum from i to j each query — O(n).
The key insight
Prefix sum array. Query = prefix[j+1] - prefix[i]. O(n) precompute, O(1) per query.
Trace it on nums=[-2,0,3,-5,2,-1]; queries: sumRange(0,2), sumRange(2,5), sumRange(0,5)
init: prefix=[0] build prefix: append cumulative sums → prefix=[0,-2,-2,1,-4,-2,-3] sumRange(0,2) = prefix[3] - prefix[0] = 1 - 0 = 1 sumRange(2,5) = prefix[6] - prefix[2] = -3 - (-2) = -1 sumRange(0,5) = prefix[6] - prefix[0] = -3 - 0 = -3 returned: [1, -1, -3]
What must stay true
sum(i..j) = prefix[j+1] - prefix[i]. Prefix stores cumulative sums.
Shape of the loop
init(nums):
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
sumRange(left, right):
return prefix[right+1] - prefix[left]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Off-by-one: prefix[0] = 0. Query (i,j) = prefix[j+1] - prefix[i].