Range sums from a prefix array
Suppose a program must answer many questions: "what is the total from slot l to slot r?" Adding a slice each time costs up to n steps per question.
Build a prefix array once, where pre[k] is the total of the first k items. It has n + 1 entries and pre[0] is 0. Any range is then one subtraction:
total of items l..r = pre[r + 1] - pre[l]pre[r + 1] holds everything up to and including r, and pre[l] holds everything before l. Subtracting leaves exactly l..r.
Building costs n steps once; every question afterwards costs one step. With 100,000 questions that is the difference between a timeout and an instant answer.
The same idea works for counting (how many of each colour so far) and for 2D grids. Watch pre fill in the visual, then see the answer line subtract two entries.
See it run
crates = [4, 2, 7, 1] pre = [0] for c in crates: pre.append(pre[-1] + c) answer = pre[4] - pre[1]
pre starts with a 0 so that the range starting at slot 0 also works.
Practice range sums from a prefix array
Exercise 1
A warehouse shelf has crates[i] crates in slot i (slots are numbered from 0). Each query [left, right] asks for the total number of crates in slots left through right, both included. Return a list with the answer to each query, in the same order. No queries gives [].
Constraints: 1 ≤ len(crates) ≤ 10^5, 0 ≤ crates[i] ≤ 1000, 0 ≤ len(queries) ≤ 10^5, 0 ≤ left ≤ right < len(crates).
Example: solution([4, 2, 7, 1], [[0, 1], [1, 3], [2, 2]]) returns [6, 10, 7].
Exercise 2
A fence has fence[i] as the colour of board i, a number from 0 to 9. Each query [left, right, colour] asks how many boards from left to right (both included) are painted colour. Return a list with one answer per query, in order.
Constraints: 1 ≤ len(fence) ≤ 10^5, 0 ≤ fence[i] ≤ 9, 0 ≤ len(queries) ≤ 10^5, 0 ≤ left ≤ right < len(fence), 0 ≤ colour ≤ 9.
Example: solution([2, 0, 2, 2, 1], [[0, 4, 2], [1, 2, 2], [4, 4, 0]]) returns [3, 1, 0].
Exercise 3
A greenhouse is a grid of trays. trays[r][c] is the number of seedlings in the tray at row r, column c. Each query [top, left, bottom, right] asks for the total seedlings in all trays from row top to row bottom and from column left to column right, all four edges included. Return a list with one answer per query, in order.
Constraints: 1 ≤ rows, columns ≤ 300, 0 ≤ trays[r][c] ≤ 100, 0 ≤ len(queries) ≤ 10^5, and every query is inside the grid with top ≤ bottom and left ≤ right.
Example: for trays = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], solution(trays, [[0, 0, 1, 1], [1, 1, 2, 2], [2, 0, 2, 2]]) returns [12, 28, 24].
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.