Intro

You have an array. Someone asks you: "What's the sum from index 3 to index 7?" Easy, you loop and add. But what if they ask $100{,}000$ such questions? Looping each time gives you $O(n \cdot q)$ where $q$ is the number of queries.

With $n = 100{,}000$ and $q = 100{,}000$, that's $10$ billion operations. Your program times out. By the end, you'll answer each query in $O(1)$ time after a single $O(n)$ preprocessing step. The technique is called prefix sums.