Reservoir ledger

A reservoir keeper writes down one number a day. The water board asks about stretches of days, over and over, and re-adding the days each time is the slow way to answer.

The problem

Each evening the keeper records the net change in the water level in centimetres: positive when the inflow wins, negative when evaporation and draw-off take more than the rain brings in, 0 on a day that ends level.

The board then sends a batch of questions. Each is a pair [start, end], 0-indexed and inclusive, asking for the sum of the daily numbers from day start to day end. There are usually far more questions than days, they arrive together once the log is closed, and they overlap and repeat freely.

Input. daily_change — a list of integers, one per day, in order. windows — a list of [start, end] pairs.

Output. A list of integers, one net change per window, in the order asked.

Example.

daily_change = [4, -1, 12, 7, -3, 9]
windows = [[0, 2], [3, 5], [2, 2], [0, 5]]  ->  [15, 13, 12, 28]

Days 0 to 2 give 4 − 1 + 12 = 15, days 3 to 5 give 13, a one-day window is that day, and the last is the whole log: 28 centimetres up.

A second example, where a window repeats and every day is a loss:

daily_change = [-5, -5, -5]
windows = [[1, 1], [1, 1], [0, 2]]  ->  [-5, -5, -15]

The second look-up costs exactly the two reads the first one cost.

Constraints.

• 1 <= len(daily_change) <= 10^5
• -10^4 <= daily_change[i] <= 10^4
• 0 <= len(windows) <= 10^5
• 0 <= start <= end < len(daily_change)

Hints

Approach

Brute force

Answer each window by adding its days: a window of length L costs L additions, so q windows over n days cost up to q · n — 10¹⁰ additions at 10⁵ each, most of them repeats.

The insight

A window total is the difference between two totals measured from the same fixed origin, so one cumulative pass lets every window be answered with a single subtraction.

Addition is associative and each day enters the running total exactly once, so total[end + 1] - total[start] cancels every day before start and keeps days start through end. Subtraction cancels a loss the same way it cancels a gain, so negative days need no care. The precondition is that the log does not change while the questions are answered: the ledger is a snapshot, and one edited day invalidates every entry after it.

Algorithm

1. Build total with n + 1 entries and total[0] = 0.
2. For each day i, set total[i + 1] = total[i] + daily_change[i].
3. For each window [start, end], take total[end + 1] - total[start].
4. Return the results in the order the windows arrived.

Complexity

Time O(n + q) — one pass builds the ledger, then constant work per window. Space O(n) for the ledger, plus the q answers.

Solution

"""Reservoir ledger — range sums answered from one cumulative prefix array."""


def cumulative(daily_change):
    """total[i] is the net change over days 0..i-1; total[0] = 0, the empty stretch."""
    total = [0] * (len(daily_change) + 1)
    for i, change in enumerate(daily_change):
        total[i + 1] = total[i] + change
    return total


def solve(daily_change, windows):
    total = cumulative(daily_change)
    # invariant: days start..end inclusive sum to total[end + 1] - total[start],
    # because every earlier day appears in both terms and cancels
    return [total[end + 1] - total[start] for start, end in windows]

TESTS = [
    (([4, -1, 12, 7, -3, 9], [[0, 2], [3, 5], [2, 2], [0, 5]]), [15, 13, 12, 28]),
    (([-5, -5, -5], [[1, 1], [1, 1], [0, 2]]), [-5, -5, -15]),
    (([9], [[0, 0]]), [9]),
    (([3, 3, 3, 3], []), []),
    (([0, 0, 0, 7], [[0, 2], [0, 3], [3, 3]]), [0, 7, 7]),
]

Pitfalls

• Indexing the ledger as if it had n entries. With the leading zero, day end is accounted for at total[end + 1]. Writing total[end] - total[start] silently returns the total for start through end − 1, so window [0, 2] on the first example gives 3 instead of 15.
• Dropping the leading zero and branching on start == 0. The branch is what gets forgotten, and in Python the mistake does not raise: total[start - 1] with start = 0 reads total[-1], the grand total, and returns a plausible wrong number.
• Rebuilding the ledger inside the question loop. That is O(q · n) again, and slower than the brute force it replaced, since it allocates an array per question.

Variants

• Bypassing a gear stage — the same sweep with products, and no stored array, because each index is asked about once.
• The bracket under the shelf — one running total suffices there, since the only window that matters is everything left of the current position.