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.
std::partial_sum(v.begin(), v.end(), out.begin()); // inclusive std::exclusive_scan(v.begin(), v.end(), out.begin(), 0);
Try it
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.
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
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
iincludesa[i]; exclusive outputistops before it, so the first output equalsinit. partial_sumvsinclusive_scan: same results for integers, butinclusive_scanmay regroup operands, so it requires an associative operation and floating-point results may differ in the last digits.partial_sumis strictly sequential and accepts any operation.inclusive_scanandexclusive_scanalso have execution-policy overloads.- Range query: with
prethe inclusive prefix array, the sum of indicesl..rispre[r] - pre[l-1](justpre[r]whenlis 0). - Type of accumulation:
partial_sumaccumulates in the value type of the input, so large sums overintcan overflow; useexclusive_scanorinclusive_scanwith a wideinitsuch as0LL. adjacent_difference: the first output is copied unchanged; elementiisa[i] - a[i-1]by default. It undoespartial_sum.- In place: passing
v.begin()as output replaces the data with its running totals. - Complexity: O(n) applications of the operation.