DSA · interactive
Prefix sums: range sums in O(1)
Add up the array once from the left, storing the running total. Then the sum of any range is one subtraction: the total up to the end minus the total before the start. Drag the range.
nums
3-1415-92653
prefix (P[i] = sum of the first i numbers)
032671235111619
P0P1P2P3P4P5P6P7P8P9P10
sum(nums[2..6]) = P[7] − P[2] = 5 − 2 = 3
Adding them one by one: 5 additions. With prefix sums: 1 subtraction, for any range.
Everything in P[7] minus everything before index 2 leaves exactly the highlighted range.
1 2 The sum from l to r is P[r+1] − P[l]: everything up to r, minus everything before l.
O(1) per query after O(n) setup.
3 4
Now solve it
In production
Tools and technologies
Running totals hide inside databases and image libraries.
Not tied to one language — use these names when you search docs or design a system.