The Range Sum Problem

Here's the setup: you have an array $a$ of $n$ integers. You receive $q$ queries, each asking for the sum of elements from index $l$ to index $r$.

For one query, you'd write a loop: start at $l$, add elements until $r$, return the sum. That's $O(r - l + 1)$ per query, which in the worst case is $O(n)$. Multiply by $q$ queries and you get $O(n \cdot q)$. When both $n$ and $q$ are large, this is too slow. You need a smarter approach.