Building the Prefix Array

Building the prefix array takes one pass through the original array: $pref[0] = 0$ $pref[i] = pref[i-1] + a[i]$ for $i$ from $1$ to $n$ Each element adds to the running total. Time: $O(n)$. Space: $O(n)$ for the prefix array. You do this once, before any queries arrive.

After that, every query becomes fast. The preprocessing cost is fixed; the per-query cost drops dramatically.