C++ <numeric>: accumulate, reduce, prefix sums

Four deposits of 1,000,000,000 paise add up to 4,000,000,000, yet std::accumulate(deposits.begin(), deposits.end(), 0) returns -294,967,296 with both compilers, and nothing warns: the initial 0 made the running total an int. Traps like this are why <numeric> is worth knowing.

std::accumulate foldsfold: Combining the elements of a range into one value with an operation, starting from an initial value: a left fold of 1, 2 and 3 with + computes ((0 + 1) + 2) + 3. std::accumulate and C++23's std::ranges::fold_left fold from the left. a range from left to right, starting from an initial value. std::reduce (C++17) computes the same kind of total but may group and reorder the additions, so it can run in parallel, and std::transform_reduce first applies a function to each element, or to each pair of two ranges. std::partial_sum and std::inclusive_scan write running totals, the prefix sumsprefix sums: An array whose position i holds the total of the first i values, with 0 at position 0, so the total of the half-open range [l, r) is prefix[r] - prefix[l], one subtraction whatever its length. std::partial_sum and std::inclusive_scan write the running totals. that answer any “total from position l to r” question with one subtraction, and std::adjacent_difference turns running totals back into values. std::iota fills a range with increasing values, and std::gcd, std::lcm and std::midpoint do integer arithmetic that is easy to get wrong by hand.

accumulate adds in the type of its initial value

Four deposits and three hours, added from different starting values:

// std::accumulate adds in the type of its initial value: 0 means int, whatever the elements are.
#include <algorithm>
#include <functional>
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<long long> deposits(4, 1'000'000'000);  // four deposits of 1,000,000,000 paise each
    std::println("accumulate with 0:   {}", std::accumulate(deposits.begin(), deposits.end(), 0));
    std::println("accumulate with 0LL: {}", std::accumulate(deposits.begin(), deposits.end(), 0LL));

    std::vector<double> hours{0.5, 0.75, 1.25};
    std::println("accumulate with 0:   {}", std::accumulate(hours.begin(), hours.end(), 0));
    std::println("accumulate with 0.0: {}", std::accumulate(hours.begin(), hours.end(), 0.0));

    // C++23's fold_left keeps the total in the type that the operation returns: int + long long is long long.
    std::println("fold_left with 0:    {} and {}", std::ranges::fold_left(deposits, 0, std::plus<>{}),
                 std::ranges::fold_left(hours, 0, std::plus<>{}));
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra accumulate_type.cpp -o accumulate_type && ./accumulate_type
g++-16 -std=c++23 -Wall -Wextra accumulate_type.cpp -o accumulate_type-gcc && ./accumulate_type-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra accumulate_type.cpp -o accumulate_type && ./accumulate_type
accumulate with 0:   -294967296
accumulate with 0LL: 4000000000
accumulate with 0:   1
accumulate with 0.0: 2.5
fold_left with 0:    4000000000 and 2.5
$ g++-16 -std=c++23 -Wall -Wextra accumulate_type.cpp -o accumulate_type-gcc && ./accumulate_type-gcc
accumulate with 0:   -294967296
accumulate with 0LL: 4000000000
accumulate with 0:   1
accumulate with 0.0: 2.5
fold_left with 0:    4000000000 and 2.5

With 0, the running total is an int. For the deposits, each addition happens in long long and the result is stored back into the int. Since C++20 that conversion is defined as wrapping round modulo 2³², so both compilers print -294,967,296 every time: a wrong answer that looks plausible at a glance. For the hours, every step cuts the double back to a whole number, so 0.5 and 0.75 vanish and only the 1 of 1.25 survives. Step through the hours, added once from 0 and once from 0.0:

Passing 0LL or 0.0 fixes both. C++23’s std::ranges::fold_left avoids the trap by design: its total takes the type that the operation returns, and adding a long long to an int returns a long long. When the elements and the initial value are both int, an overflowing sum is not even wrapped: it is undefined behaviour.

The same rule explains a common compile error: std::accumulate(words.begin(), words.end(), "") on a vector of strings does not compile, because the initial value makes the total a const char*, and a joined std::string cannot be stored in one. With std::string{} as the initial value it compiles and joins the words. Write the initial value in the type you want the total to have.

reduce may regroup the additions, so the operation must allow it

std::reduce returns what accumulate would, as long as the operation does not care how the values are grouped or ordered. The standard lets it apply the operation in an unspecified order, so that it can split the range across threads when given an execution policyAn argument such as std::execution::par (C++17, header <execution>) that permits a standard algorithm to spread its work over several threads, or to use vector instructions., and it notes that the result is then nondeterministic for operations such as floating-point addition. For integers that changes nothing; for float and double the last digits can change, and with large and small values mixed, much more than the last digits. Step through eight whole numbers added in two orders:

Use reduce when the operation is associative and commutative, such as integer addition, a maximum or a bitwise or, and keep accumulate when the order is part of the result: subtraction, joining strings, or floating-point totals that must come out the same everywhere. Three questions decide between the three folds:

Prefix sums answer range totals with one subtraction

Eight days of rain and their prefix sums; the program builds them and answers two questions:

// Prefix sums answer "what is the total from day l to day r?" with one subtraction.
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<long long> rain{3, 1, 4, 1, 5, 9, 2, 6};  // millimetres of rain on days 0 to 7

    // prefix[i] is the total of the first i days, so prefix[0] = 0 and prefix has one element more than rain.
    std::vector<long long> prefix(rain.size() + 1, 0);
    std::partial_sum(rain.begin(), rain.end(), prefix.begin() + 1);
    std::println("prefix: {}", prefix);

    // The total of days [l, r) is prefix[r] - prefix[l]: no loop, whatever the length.
    auto total = [&](std::size_t l, std::size_t r) { return prefix[r] - prefix[l]; };
    std::println("days 2 to 5: {}", total(2, 6));
    std::println("all 8 days: {}", total(0, 8));

    // adjacent_difference undoes partial_sum: it gives back the daily values.
    std::vector<long long> back(prefix.size());
    std::adjacent_difference(prefix.begin(), prefix.end(), back.begin());
    std::println("adjacent_difference of prefix: {}", back);

    // C++17's scans: inclusive_scan matches partial_sum; exclusive_scan starts from an initial value instead.
    std::vector<long long> inc(rain.size()), exc(rain.size());
    std::inclusive_scan(rain.begin(), rain.end(), inc.begin());
    std::exclusive_scan(rain.begin(), rain.end(), exc.begin(), 0LL);
    std::println("inclusive_scan: {}", inc);
    std::println("exclusive_scan: {}", exc);
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra range_queries.cpp -o range_queries && ./range_queries
g++-16 -std=c++23 -Wall -Wextra range_queries.cpp -o range_queries-gcc && ./range_queries-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra range_queries.cpp -o range_queries && ./range_queries
prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
days 2 to 5: 19
all 8 days: 31
adjacent_difference of prefix: [0, 3, 1, 4, 1, 5, 9, 2, 6]
inclusive_scan: [3, 4, 8, 9, 14, 23, 25, 31]
exclusive_scan: [0, 3, 4, 8, 9, 14, 23, 25]
$ g++-16 -std=c++23 -Wall -Wextra range_queries.cpp -o range_queries-gcc && ./range_queries-gcc
prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
days 2 to 5: 19
all 8 days: 31
adjacent_difference of prefix: [0, 3, 1, 4, 1, 5, 9, 2, 6]
inclusive_scan: [3, 4, 8, 9, 14, 23, 25, 31]
exclusive_scan: [0, 3, 4, 8, 9, 14, 23, 25]

prefix[i] holds the total of the first i values and prefix[0] is 0, so the total of the half-open range [l, r) is prefix[r] - prefix[l]: one subtraction, however long the range. Building the array takes one pass with std::partial_sum, written from position 1. std::adjacent_difference reverses it, which is why the round trip prints the daily values again, behind the 0. C++17’s std::inclusive_scan writes the same running totals as partial_sum, and std::exclusive_scan writes the total before each position, starting from an initial value. Step through the build and two questions:

The cost is one pass to build the array and one subtraction per question, against a walk over the whole range for every question when you add it up again. That trade is why prefix sums are the standard tool for many questions about data that does not change. When values change between questions, the array would have to be rebuilt; a Fenwick tree handles both an update and a range total in O(log n) steps.

gcd, lcm, midpoint and iota do small integer jobs

Four more functions of <numeric> handle integer arithmetic that hand-written code often gets wrong:

• std::gcd(m, n) (C++17) returns the greatest common divisor of the absolute values, and 0 when both are 0.
• std::lcm(m, n) (C++17) returns the least common multiple, which must fit in the result type.
• std::midpoint(a, b) (C++20) returns half the sum without overflowing, rounded towards a for integers.
• std::iota(first, last, value) fills a range with value, value + 1 and so on; C++23 adds std::ranges::iota.

// std::iota fills a range with increasing values; std::gcd, std::lcm and std::midpoint do small integer jobs.
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> seats(6);
    std::iota(seats.begin(), seats.end(), 101);  // 101, 102, ..., 106
    std::println("seats: {}", seats);

    // The largest square tile that covers a 48 x 18 floor exactly, with no tile cut.
    std::println("gcd(48, 18) = {}", std::gcd(48, 18));
    // Two lights that blink every 4 and every 6 seconds blink together every lcm seconds.
    std::println("lcm(4, 6) = {}", std::lcm(4, 6));
    // Half the sum, computed in a way that cannot overflow.
    std::println("midpoint(10, 20) = {}", std::midpoint(10, 20));
}

seats: [101, 102, 103, 104, 105, 106]
gcd(48, 18) = 6
lcm(4, 6) = 12
midpoint(10, 20) = 15

Each job is one call: seats from 101, a tile of side 6 for a 48 by 18 floor, lights that blink together every 12 seconds and 15 halfway between 10 and 20. Small positive test values like these never reach the edges: negative numbers, zeros, results too large for their type and odd sums.

Practise: totals, types and ranges

The questions below start where your answers have been weakest, and each choice names the slip it guards against.

Prefix sums at scale: grids, overflow budgets and timed queries Pro: opens with a Pro, Premium or Ultimate pass

reduce, transform_reduce, gcd, lcm and midpoint: the traps, reproduced Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• std::accumulate adds in the type of its initial value: write 0LL or 0.0, never a bare 0, for large or fractional sums.
• std::reduce may regroup the additions, so floating-point totals can differ from accumulate.
• Prefix sums turn the total of [l, r) into prefix[r] - prefix[l].
• gcd, lcm and midpoint handle signs and overflow for you, except that the lcm itself must fit in its result type.