Running Totals and Range Sums

Prefix Sums, lesson 1 of 3

Running Totals and Range Sums

Build a prefix array once and answer every range sum with one subtraction.

10 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Say a problem asks for the sum of nums[l..r] again and again, for many different ranges. The obvious way loops over the range each time: O(n) per question, O(n · q) for q questions.

A prefix sum array fixes this. Walk the array once and record the running total. With those totals saved, every range sum becomes one subtraction.

Think of a car's odometer. To know how far you drove between two towns you don't re-drive the road; you subtract the two odometer readings.

The picture. Put a 0 in front, so P[i] is the sum of the first i elements (nums[0:i]):

index:      0   1   2   3   4
nums:     [ 3,  1,  4,  1,  5 ]

P:      [ 0,  3,  4,  8,  9, 14 ]
i:        0   1   2   3   4   5

P has n + 1 entries. The sum of nums[l..r] (inclusive) is everything up to r minus everything before l:

sum(nums[l..r]) = P[r + 1] - P[l]

For l = 1, r = 3: P[4] - P[1] = 9 - 3 = 6, which is 1 + 4 + 1. ✔

Example

Build it by hand, then with accumulate

accumulate(nums) alone gives the running totals without the leading 0; initial=0 adds it. Try list(accumulate(nums)) to see the difference.

Quiz

What does this print?

Costs. Building P is one pass: O(n) time, O(n) extra space. After that each query is O(1), so q queries cost O(n + q) instead of O(n · q).

How to recognise it in an interview:

  • "sum of a subarray / range", asked many times
  • "left sum vs right sum" at each index (you know the total, so right = total - left - current)
  • "number of subarrays with sum ..." (next lesson)
  • the array doesn't change between queries (if it does, you need a Fenwick / segment tree)

Prefix sums also work for anything you can "undo": running XOR (a ^ b ^ b == a), counts of a character, or +1/-1 balances.

Quiz

P has a leading 0 (P[i] = sum of nums[:i]). Which expression is the sum of nums[l..r], both ends included?

Exercise

Answer many range queries

Write range_sums(nums, queries). Each query is a pair (l, r); return a list with the sum of nums[l..r] (inclusive) for each query, in order.

Build a prefix array once, then answer each query with a single subtraction. Don't call sum() on a slice per query.