Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The std::partial_sum and std::inclusive_scan algorithms

Reference for C++ std::partial_sum, inclusive_scan, exclusive_scan and adjacent_difference: running totals, prefix sums, differences and their rules.

A prefix sum (running total) replaces each element with the sum of everything up to it. std::partial_sum (C++98, <numeric>) computes it left to right: output element i is a[0] + a[1] + ... + a[i]. C++17 added std::inclusive_scan, the same result but allowed to be evaluated in any grouping, and std::exclusive_scan, where output element i leaves out a[i] and starts from an initial value.

The inverse operation is std::adjacent_difference, which turns running totals back into the original values. Prefix sums are the standard tool for answering "sum of a range" queries quickly after one O(n) pass.

C++
std::partial_sum(v.begin(), v.end(), out.begin());      // inclusive
std::exclusive_scan(v.begin(), v.end(), out.begin(), 0);

Try it

C++ Inclusive, exclusive and range sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ adjacent_difference is the inverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template<class InIt, class OutIt>
OutIt partial_sum(InIt first, InIt last, OutIt d_first);
template<class InIt, class OutIt, class BinOp>
OutIt partial_sum(InIt first, InIt last, OutIt d_first, BinOp op);

template<class InIt, class OutIt>
OutIt inclusive_scan(InIt first, InIt last, OutIt d_first);
template<class InIt, class OutIt, class BinOp, class T>
OutIt inclusive_scan(InIt first, InIt last, OutIt d_first, BinOp op, T init);

template<class InIt, class OutIt, class T>
OutIt exclusive_scan(InIt first, InIt last, OutIt d_first, T init);

template<class InIt, class OutIt>
OutIt adjacent_difference(InIt first, InIt last, OutIt d_first);
Name Description
first, last Input range.
d_first Output start; may equal first (in place).
op Binary operation, default +. For inclusive_scan and exclusive_scan it must be associative.
init Initial value: the first output of exclusive_scan; for inclusive_scan it is folded into every result.

Returns: an iterator one past the last element written.

Errors / undefined behavior: the output must have room for last - first elements; signed overflow is undefined; d_first may only overlap the input exactly (in place).

Usage notes

  • Inclusive vs exclusive: inclusive output i includes a[i]; exclusive output i stops before it, so the first output equals init.
  • partial_sum vs inclusive_scan: same results for integers, but inclusive_scan may regroup operands, so it requires an associative operation and floating-point results may differ in the last digits. partial_sum is strictly sequential and accepts any operation. inclusive_scan and exclusive_scan also have execution-policy overloads.
  • Range query: with pre the inclusive prefix array, the sum of indices l..r is pre[r] - pre[l-1] (just pre[r] when l is 0).
  • Type of accumulation: partial_sum accumulates in the value type of the input, so large sums over int can overflow; use exclusive_scan or inclusive_scan with a wide init such as 0LL.
  • adjacent_difference: the first output is copied unchanged; element i is a[i] - a[i-1] by default. It undoes partial_sum.
  • In place: passing v.begin() as output replaces the data with its running totals.
  • Complexity: O(n) applications of the operation.