The Range Sum Problem

Here's a problem you'll see constantly: given an array, answer many queries asking for the sum of elements from index $l$ to $r$.

The naive approach loops from $l$ to $r$ and adds up elements. Each query takes $O(n)$ time. With $q$ queries, that's $O(nq)$ total.

If $n = 100{,}000$ and $q = 100{,}000$, you're doing $10$ billion operations. That's too slow. There's a better way.