Answering Range Queries

Here's the key formula. To find the sum from index $l$ to $r$: $\text{sum}(l, r) = pref[r] - pref[l-1]$ Why does this work? $pref[r]$ contains $a[1] + a[2] + \ldots + a[r]$. Subtracting $pref[l-1]$ removes $a[1] + \ldots + a[l-1]$, leaving exactly $a[l] + \ldots + a[r]$. One subtraction. $O(1)$ per query.

With $q$ queries, total time is $O(n + q)$ instead of $O(n \cdot q)$. For $n = q = 10^5$, that's $2 \times 10^5$ operations instead of $10^{10}$.