Build prefix sums step by step, then answer range queries instantly!
A prefix sum array stores cumulative sums. prefix[i] =
sum of all elements from index 0 to i-1.
To find sum of range [L, R]: prefix[R+1] - prefix[L]
Without prefix sum: Each query takes O(n) time - sum all elements in range.
With prefix sum: Each query takes O(1) time - just one subtraction!
Building the prefix array: O(n) once. Then unlimited queries in O(1) each!