Pay once, answer fast
Build running totals once, then answer any range sum with one subtraction. About 9 minutes.
A balance after every day
Your bank app is asked a thousand times: "how much did I spend from day 3 to day 7?" Adding those days up for every question is slow when the ranges are long.
Instead, keep a running balance: the total spent up to the end of each day, with a 0 at the very start for "before day one". You make this list once, in one walk. It's the running total from earlier, with that extra 0 in front.
Any range is two balances subtracted
The spending from day 3 to day 7 is the balance after day 7, minus the balance before day 3. Everything before day 3 cancels out. That's one subtraction, however long the range is.
The one fiddly part is off-by-one: with the 0 in front, "the balance after day 7" sits one box to the right of day 7. Trace one small example by hand and it clicks.
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
# each question: boxes l to r, inclusive
return [prefix[r + 1] - prefix[l]
for l, r in queries]Total of boxes 1 to 3: the balance after box 3 (10) minus the balance before box 1 (2) = 8.
The numbers are 3, 2, 7, 1, so the running balances (with 0 in front) are 0, 3, 5, 12, 13. What's the total of boxes 1 and 2?
- A9
- B10
- C7
Show the answer
9. The balance after box 2 (12) minus the balance before box 1 (3): 9, which is 2 + 7.
Range sums
You get a list of numbers and a list of questions. Each question is [l, r] and asks for nums[l] + nums[l + 1] + … + nums[r]. Return the answers in order.
nums = [2, 4, 1, 3, 5], queries = [[0, 2], [1, 3], [4, 4]] → [7, 8, 5]
1 ≤ n ≤ 100,000 · 0 ≤ queries ≤ 100,000 · 0 ≤ l ≤ r < n · −10^9 ≤ each value ≤ 10^9 · answers can pass 2^31: use longs