## partial_sum

partial_sum

Category: algorithms

Component type: function

### Prototype

Partial_sum is an overloaded name; there are actually two partial_sum functions.

```template <class InputIterator, class OutputIterator> OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result); template <class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);```

### Description

Partial_sum calculates a generalized partial sum: *first is assigned to *result, the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. [1]

More precisely, a running sum is first initialized to *first and assigned to *result. For each iterator i in [first + 1, last), in order from beginning to end, the sum is updated by sum = sum + *i (in the first version) or sum = binary_op(sum, *i) (in the second version) and is assigned to *(result + (i – first)). [2]

### Definition

Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version:

• InputIterator is a model of Input Iterator.

• OutputIterator is a model of Output Iterator.

• If x and y are objects of InputIterator's value type, then x + y is defined.

• The return type of x + y is convertible to InputIterator's value type.

• InputIterator's value type is convertible to a type in OutputIterator's set of value types.

For the second version:

• InputIterator is a model of Input Iterator.

• OutputIterator is a model of Output Iterator.

• BinaryFunction is a model of BinaryFunction.

• InputIterator's value type is convertible to BinaryFunction's first argument type and second argument type.

• BinaryFunction's result type is convertible to InputIterator's value type.

• InputIterator's value type is convertible to a type in OutputIterator's set of value types.

### Preconditions

• [first, last) is a valid range.

• [result, result + (last – first)) is a valid range.

### Complexity

Linear. Zero applications of the binary operation if [first, last) is a empty range, otherwise exactly (last – first) – 1 applications.

### Example

```int main() {  const int N = 10;  int A[N];  fill(A, A+N, 1);  cout << "A: ";  copy(A, A+N, ostream_iterator<int>(cout, " "));  cout << endl;  cout << "Partial sums of A: ";  partial_sum(A, A+N, ostream_iterator<int>(cout, " "));  cout << endl; }```

### Notes

[1] Note that result is permitted to be the same iterator as first. This is useful for computing partial sums "in place".

[2] The binary operation is not required to be either associative or commutative: the order of all operations is specified.