Prefix Sums - Walkthrough

Build prefix sums for $arr = [3, 1, 4, 1, 5, 9]$. Let $prefix[0] = 0$ (empty prefix). $prefix[1] = 3$, $prefix[2] = 4$, $prefix[3] = 8$, $prefix[4] = 9$, $prefix[5] = 14$, $prefix[6] = 23$.

Now answer: sum of $arr[2..4]$ (0-indexed)? That's $prefix[5] - prefix[2] = 14 - 4 = 10$. Check: $4 + 1 + 5 = 10$. Correct! Each query is $O(1)$ after $O(n)$ preprocessing. For $q$ queries, this beats the naive $O(nq)$ approach.