Card 02/ 08
Answer Many Rainfall Questions Without Re-Adding the Days
Summing each question's days again costs n per question; one pass of running totals makes every question one subtraction.
Building a prefix array once turns each question about a range into one subtraction, so many questions over the same data cost one pass plus one step each. A weather station logged a week of rainfall in millimetres, 4 0 7 2 0 5 1, from day 0 to day 6, and three questions arrive: the rain over days 0 to 2, over days 2 to 5, and over days 3 to 6.
The brute force re-adds each question's days. A question can span the whole log, so q questions over n days cost O(n × q), and the repeated work is plain: day 2 is added for the first two questions, and days 3, 4 and 5 for the last two. With a year of readings and thousands of questions, the same days are added thousands of times.
The prefix array adds each day once. Its entries for this week are 0 4 4 11 13 13 18 19, and the rain over days i to j inclusive is p[j + 1] − p[i].
Re-addingO(n × q) time
For each question, loop from its first day to its last and add the rain. Days shared by several questions are added again for each.
Prefix arrayO(n + q) time
One pass builds the running totals. Each question then subtracts two of them, whatever its length.
Each question reads two entries of the prefix array:
| Question | Days | Formula | Rain |
|---|---|---|---|
| First | 0 to 2 | p[3] − p[0] = 11 − 0 | 11 mm |
| Second | 2 to 5 | p[6] − p[2] = 18 − 4 | 14 mm |
| Third | 3 to 6 | p[7] − p[3] = 19 − 11 | 8 mm |
The listing answers the questions both ways and counts the additions each makes.
def answer_by_readding(rain: list[int], questions: list[tuple[int, int]]) -> tuple[list[int], int]:
answers, additions = [], 0
for first, last in questions:
total = 0
for day in range(first, last + 1):
total += rain[day]
additions += 1
answers.append(total)
return answers, additions
def answer_by_prefix(rain: list[int], questions: list[tuple[int, int]]) -> tuple[list[int], int]:
prefix = [0]
for millimetres in rain:
prefix.append(prefix[-1] + millimetres)
answers = [prefix[last + 1] - prefix[first] for first, last in questions]
return answers, len(rain)
rain = [4, 0, 7, 2, 0, 5, 1]
questions = [(0, 2), (2, 5), (3, 6)]
print("re-adding:", *answer_by_readding(rain, questions))
print("prefix: ", *answer_by_prefix(rain, questions))re-adding: [11, 14, 8] 11
prefix: [11, 14, 8] 7Both give 11, 14 and 8 millimetres. Re-adding made 11 additions for three questions, and the count grows with every question; the prefix array made 7, one per day, and each question added two reads. The cost is O(n + q) time and O(n) extra space for the array.
← → move through sections and cards