Step 5 of 6

Prefix sums

If you'll ask "what's the sum of elements l..r?" many times, adding them up each time costs O(n) per question. Instead, precompute prefix sums once: pre[i] is the sum of the first i elements. Then any range sum is one subtraction.

v   =     3   1   4   1   5
pre = 0   3   4   8   9  14

sum(1..3) = pre[4] - pre[1] = 9 - 3 = 6     (1 + 4 + 1)

#include <iostream>
#include <vector>

int main() {
    std::vector<int> rain = {3, 0, 12, 5, 0, 7, 2};       // mm per day
    std::vector<long long> pre(rain.size() + 1, 0);
    for (std::size_t i = 0; i < rain.size(); i++) pre[i + 1] = pre[i] + rain[i];

    auto total = [&pre](int l, int r) { return pre[r + 1] - pre[l]; };   // inclusive
    std::cout << "days 0-6: " << total(0, 6) << "\n";
    std::cout << "days 2-3: " << total(2, 3) << "\n";
    std::cout << "day 4: " << total(4, 4) << "\n";
}

days 0-6: 29
days 2-3: 17
day 4: 0

How it works

• pre has one more entry than the data, with pre[0] = 0. That extra zero means a range starting at index 0 needs no special case.
• pre[r + 1] is the sum of everything up to and including r; subtracting pre[l] removes everything before l.
• Use long long for the sums: 200,000 values can easily add up past the int limit.

O(n) setup, then O(1) per query. The same trick works for counts ("how many errors between 9:00 and 9:15?"), 2D grids (summed-area tables, used in image processing) and time series.

Your turn: write class RangeSum with a constructor taking the values and long long sum(int l, int r) const for the inclusive range. The test runs 200,000 queries on 200,000 values.

Previous: Two pointers Next: Challenge: sliding window