Write down a running total once, then answer "what is the sum of this range?" with one subtraction instead of re-adding.
Used for
Now tap the end number.
Now tap the end number.
Now tap the end number.
Now tap the end number.
10 − 3 = 7
check: 1 + 4 + 2 = 7
Now tap the end number.
10 − 3 = 7
check: 1 + 4 + 2 = 7
Step 1 of 5
Question: what is 1 + 4 + 2? Adding three numbers is easy. But if someone asks 1,000 range questions, you re-add the same numbers again and again.
Step 2 of 5
The fix: walk left to right once and write a running total under each number. Each bottom box means everything from the start up to here. The small sum under it shows how it was built.
Step 3 of 5
Want 1 + 4 + 2? Look at the running total under the 2: it is 10. That is too much, because it counts 3 + 1 + 4 + 2 and includes an extra 3 at the front.
Step 4 of 5
Remove the extra part. The running total just before your range is 3, so 10 − 3 = 7. That is two lookups and one subtraction, however long the range is. This list of running totals is called a prefix sum.
Step 5 of 5
Your turn. Tap a start number, then an end number. Try starting at the first number to see the "nothing before" case.
ArraysMaximum subarray problemFenwick Tree / Binary Indexed TreeSegment Tree
// Running totals: prefix[i] = nums[0] + ... + nums[i - 1], with prefix[0] = 0.const prefix = [0];for (const n of nums) prefix.push(prefix.at(-1) + n);const rangeSum = (start, end) => prefix[end + 1] - prefix[start]; // nums[start..end]// Variant: count subarrays that add up to k, using a Map of running totals seen so far.function subarraySum(nums, k) { const count = new Map([[0, 1]]); let sum = 0, hits = 0; for (const n of nums) { sum += n; hits += count.get(sum - k) ?? 0; count.set(sum, (count.get(sum) ?? 0) + 1); } return hits;}