Answer many range-total questions quickly

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so each query is O(1).

Python 3.13
from itertools import accumulate
sales = [3, 1, 4, 1, 5]
prefix = [0, *accumulate(sales)]
l, r = 1, 3
print(____)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A prefix[r + 1] - prefix[l]

Right: everything up to day r, minus everything before day l.

Days 1 to 3 hold 1, 4 and 1; the prefix difference gives that total with one subtraction.

Why not the others?
  • B prefix[r] - prefix[l]. That stops one day short and misses day r.
  • C sum(sales[l:r]). Correct only for the half-open range and still O(n) per query.

30-second answer

Build prefix sums once: prefix[i] is the total of the first i days. The total from l to r is prefix[r + 1] - prefix[l], one subtraction per query. That is O(n + q) time instead of O(n·q) for summing each range separately, and O(n) extra space.

Practise saying it · 30 s. No recording, just a timer

Explain prefix sums for range queries.

Say your answer out loud, then check which of these points you covered:

  • Build once O(n)
  • Each query O(1)
  • Off-by-one with a leading 0

Deep dive

The extra leading 0 in prefix removes the special case for l = 0.

For a 2D grid, a 2D prefix table answers rectangle totals in O(1) each.

If sales change between queries, use a Fenwick tree or segment tree: O(log n) per update and query.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from itertools import accumulate


def range_totals(sales: list[int],
                 queries: list[list[int]]) -> list[int]:
    prefix = [0, *accumulate(sales)]  # total of the first i days
    return [prefix[hi + 1] - prefix[lo] for lo, hi in queries]

Common mistakes

  • Off-by-one: the right end is prefix[r + 1], not prefix[r].
  • Rebuilding the prefix sums for every query.

Senior take & follow-ups

Say the before and after costs: O(n·q) down to O(n + q). That trade is the point of the question.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if values are updated?

    Show hint

    A Fenwick tree gives O(log n) updates and range sums.

  2. How do you count ranges with a given total?

    Show hint

    Prefix sums plus a hash map of earlier prefixes, O(n).

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.