Range Sum Query - Immutable
easyTime: O(1)Space: O(n)
Recognize the pattern
precompute range sumsO(1) queries after preprocessingprefix sum
Brute force idea
Sum from i to j each query — O(n).
Better approach
Prefix sum array. Query = prefix[j+1] - prefix[i]. O(n) precompute, O(1) per query.
Key invariant
sum(i..j) = prefix[j+1] - prefix[i]. Prefix stores cumulative sums.
Watch out for
Off-by-one: prefix[0] = 0. Query (i,j) = prefix[j+1] - prefix[i].