# 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 InputIterator.
• `OutputIterator` is a model of OutputIterator.
• 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 InputIterator.
• `OutputIterator` is a model of OutputIterator.
• `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.

`adjacent_difference`, `accumulate`, `inner_product`, `count`