Imagine you run a small bakery. Every morning, your accountant emails you a spreadsheet: one row per day, one column for revenue. Monday was $300, Tuesday $100, Wednesday $400, Thursday $100, Friday $500, Saturday $900, Sunday $200, next Monday $600.

Simple enough. But then your business partner calls. “What was total revenue from Tuesday through Friday?” You drag-select four cells, mentally add 100 + 400 + 100 + 500. Got it: $1,100.

She calls back. “Actually, Wednesday through Sunday?” You add five numbers again from scratch. “One more — Monday through Saturday?” Six numbers. “And what about the whole week?” Eight numbers.

Fifty questions later, you notice something maddening. Every time she asks a new question, you start adding from zero. The subtotals you computed five minutes ago? Useless. You can't reuse any of them because each query spans a different range.

This is exactly the problem your code faces with an array like [3, 1, 4, 1, 5, 9, 2, 6]. Someone asks “what's the sum from index 1 to 4?” You loop through and add. They ask “what about 0 to 5?” You loop again. Every query costs O(n) — and if there are Q queries, the total work is O(n * Q).

For 10,000 elements and 50 queries, that's half a million additions. For a million elements and a thousand queries? A billion. Your CPU is doing the same arithmetic over and over, like an accountant who refuses to use a running total.

Can you spot the waste?

Three queries. Same array. Every time, you start adding from scratch.

Watch the operations counter climb — then ask yourself: am I doing the same additions over and over?

That running total you just built — where each cell holds the cumulative sum of everything before it — has a name in algorithm design. It's called a prefix sum array, and it's one of the most leveraged data structures in competitive programming.

Here's the concrete picture. Start with your original array:

arr = [3, 1, 4, 1, 5]

Now build the prefix array by accumulating from left to right, starting with a 0 at position zero:

prefix = [0, 3, 4, 8, 9, 14]

Each entry in prefix tells you the total of all elements before that index. prefix[0] = 0 means “before the first element, nothing has been added.” prefix[3] = 8 means arr[0] + arr[1] + arr[2] = 3 + 1 + 4 = 8. prefix[5] = 14 means the entire array sums to 14.

Now the magic: to get the sum from index 1 to index 3 (that's arr[1] + arr[2] + arr[3] = 1 + 4 + 1 = 6), you don't add anything. You subtract:

prefix[4] - prefix[1] = 9 - 3 = 6

Why does subtraction work? Because prefix[4] holds the sum of elements 0 through 3, and prefix[1] holds the sum of element 0 alone. Subtracting peels away the portion you don't want, leaving exactly the range you asked for. It's the same reason you can find Tuesday-through-Friday revenue by subtracting Monday's running total from Friday's running total.

One subtraction. Two array lookups. No loops. O(1).

That prefix[0] = 0 at the base isn't arbitrary — it's doing critical structural work. Without it, computing sum(0, r) (a range starting at the very beginning) would require a special case: you'd have no prefix[-1] to subtract. The sentinel eliminates the edge case entirely. prefix[r+1] - prefix[0] is always valid, always correct, and always the same formula as any other range.

This pattern — spend time upfront to precompute, then answer each query instantly — is called the precomputation trade-off, and it's one of the most fundamental ideas in algorithm design. You'll meet it again in difference arrays, 2D prefix sums, sparse tables, and anywhere the question is “what happened between two points?”

The key insight isn't the formula. It's the economics: paying O(n) once to unlock O(1) per query is a phenomenal deal whenever Q is large. And in interviews, Q is almost always large.