Prefix Sums: Range Totals in O(1)

The problem

You have a year of daily sales and many questions like “total sales from day 30 to day 90?”. Adding 61 numbers for every question is slow when there are thousands of questions.

Running totals

Make a prefix sum array: prefix[i] is the total of the first i items. Then the sum from index i to j (both included) is prefix[j + 1] - prefix[i]:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> sales = {5, 2, 7, 1, 4};
    vector<long long> prefix(sales.size() + 1, 0);
    for (size_t i = 0; i < sales.size(); i++)
        prefix[i + 1] = prefix[i] + sales[i];

    for (long long p : prefix) cout << p << ' ';
    cout << endl;

    auto rangeSum = [&](int i, int j) { return prefix[j + 1] - prefix[i]; };
    cout << "sum(1..3) = " << rangeSum(1, 3) << endl;   // 2 + 7 + 1
    cout << "sum(0..4) = " << rangeSum(0, 4) << endl;
    return 0;
}

Output

0 5 7 14 15 19 
sum(1..3) = 10
sum(0..4) = 19

Think of it like this: A car's odometer: to know how far you drove between Monday and Friday, subtract Monday's reading from Friday's.

Tip: auto rangeSum = [&](int i, int j) { ... }; is a lambda: a small function written inside main. [&] lets it use prefix.