Prefix Sum

Do one pass up front so every later question takes a single subtraction.

The idea

Think of a bank statement showing a running balance after every transaction. How much did you spend between transaction 3 and transaction 6? You do not re-add the spending: you take the balance after #6 and subtract the balance before #3.

A prefix sum array p is that running balance: p[i] is the sum of the first i numbers. The sum of nums[l..r] is then p[r+1] − p[l]. We add one extra slot p[0] = 0 (the sum of nothing) so the formula works even when l is 0.

Watch it work

Try it

Common mistakes

How fast is it?

Build: O(n) time once. Each query: O(1). Space: O(n) for the prefix array. Without it, every query would re-add up to n numbers (O(n) each).