Range Sum Query - Immutable
easyTime: O(1)Space: O(n)
Signals to notice
precompute range sumsO(1) queries after preprocessingprefix sum
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.
What must stay true
sum(i..j) = prefix[j+1] - prefix[i]. Prefix stores cumulative sums.
Easy way to go wrong
Off-by-one: prefix[0] = 0. Query (i,j) = prefix[j+1] - prefix[i].