Syllabus Lesson 54 of 141 · Speed without the cache
Speed without the cache

Precompute once

Why it matters "Total of X between two points" is one of the most common questions in reporting code. Answering each one by adding up the range is slow; keeping a total for every point can be too big. There is a route between the two.

A shop keeps 60,000 days of sales on a metered store, handed to you as a Tape. Finance sends a batch of 50 questions at once: "total sales from day a up to day b". You run on a small worker with very little spare memory.

Running total (prefix sum): the sum of everything before a position. The total of a window is the running total at its end minus the running total at its start.

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
Your turn

Write range_totals(tape, queries). tape is a Tape of daily sales (whole numbers). queries is a list of (start, end) pairs with 0 <= start <= end <= len(tape). Return a list with the total of tape[start:end] for each query, in the order given. Budgets: read the tape at most once (60,100 reads for 60,000 days and 50 queries), and use at most 100,000 bytes of working memory while your function runs (measured with tracemalloc; a running total for every day, or even a plain list of the 60,000 values, is well over 100,000 bytes). The questions all arrive together, before you read the data.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus