The Core Idea

Here's why prefix sums work. The sum from index $l$ to $r$ equals: $sum(l, r) = prefix[r+1] - prefix[l]$ Think about it: $prefix[r+1]$ contains everything from $0$ to $r$.

Subtracting $prefix[l]$ removes everything from $0$ to $l-1$. What's left is exactly the sum from $l$ to $r$. Two array lookups and one subtraction. That's $O(1)$ per query, no matter how big the range.