# Prefix Sums

## Groups

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator `

**inclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result);

template <typename InputIterator, typename OutputIterator> OutputIterator **inclusive_scan**(InputIterator first, InputIterator last, OutputIterator result);

template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator **inclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op);

template <typename InputIterator, typename OutputIterator, typename AssociativeOperator> OutputIterator **inclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op);

template <typename DerivedPolicy, typename InputIterator, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator **exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result);

template <typename InputIterator, typename OutputIterator> OutputIterator **exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result);

template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T> _CCCL_HOST_DEVICE OutputIterator **exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, T init);

template <typename InputIterator, typename OutputIterator, typename T> OutputIterator **exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, T init);

template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator **exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op);

template <typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator> OutputIterator **exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op);

## Functions

### Function `inclusive_scan`

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator `

**inclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result);`inclusive_scan`

computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, `*first`

is assigned to `*result`

and the sum of `*first`

and `*(first + 1)`

is assigned to `*(result + 1)`

, and so on. This version of `inclusive_scan`

assumes plus as the associative operator. When the input and output sequences are the same, the scan is performed in-place.

`inclusive_scan`

is similar to `std::partial_sum`

in the STL. The primary difference between the two functions is that `std::partial_sum`

guarantees a serial summation order, while `inclusive_scan`

requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `inclusive_scan`

to compute an in-place prefix sum using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::inclusive_scan(thrust::host, data, data + 6, data); // in-place scan
// data is now {1, 1, 3, 5, 6, 9}
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined. If`T`

is`OutputIterator's`

`value_type`

, then`T(0)`

is defined.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `inclusive_scan`

` template <typename InputIterator, typename OutputIterator> OutputIterator `

**inclusive_scan**(InputIterator first, InputIterator last, OutputIterator result);`inclusive_scan`

computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, `*first`

is assigned to `*result`

and the sum of `*first`

and `*(first + 1)`

is assigned to `*(result + 1)`

, and so on. This version of `inclusive_scan`

assumes plus as the associative operator. When the input and output sequences are the same, the scan is performed in-place.

`inclusive_scan`

is similar to `std::partial_sum`

in the STL. The primary difference between the two functions is that `std::partial_sum`

guarantees a serial summation order, while `inclusive_scan`

requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use `inclusive_scan`

```
#include <thrust/scan.h>
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::inclusive_scan(data, data + 6, data); // in-place scan
// data is now {1, 1, 3, 5, 6, 9}
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined. If`T`

is`OutputIterator's`

`value_type`

, then`T(0)`

is defined.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `inclusive_scan`

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator `

**inclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op);`inclusive_scan`

computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

`inclusive_scan`

is similar to `std::partial_sum`

in the STL. The primary difference between the two functions is that `std::partial_sum`

guarantees a serial summation order, while `inclusive_scan`

requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `inclusive_scan`

to compute an in-place prefix sum using the `thrust::host`

execution policy for parallelization:

```
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
thrust::maximum<int> binary_op;
thrust::inclusive_scan(thrust::host, data, data + 10, data, binary_op); // in-place scan
// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator and`OutputIterator`

`OutputIterator's`

`value_type`

is convertible to both`AssociativeOperator's`

`first_argument_type`

and`second_argument_type`

.is a model of Binary Function and`AssociativeOperator`

`AssociativeOperator's`

`result_type`

is convertible to`OutputIterator's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The associatve operator used to ‘sum’ values.`binary_op`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `inclusive_scan`

` template <typename InputIterator, typename OutputIterator, typename AssociativeOperator> OutputIterator `

**inclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op);`inclusive_scan`

computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

`inclusive_scan`

is similar to `std::partial_sum`

in the STL. The primary difference between the two functions is that `std::partial_sum`

guarantees a serial summation order, while `inclusive_scan`

requires associativity of the binary operation to parallelize the prefix sum.

The following code snippet demonstrates how to use `inclusive_scan`

```
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
thrust::maximum<int> binary_op;
thrust::inclusive_scan(data, data + 10, data, binary_op); // in-place scan
// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator and`OutputIterator`

`OutputIterator's`

`value_type`

is convertible to both`AssociativeOperator's`

`first_argument_type`

and`second_argument_type`

.is a model of Binary Function and`AssociativeOperator`

`AssociativeOperator's`

`result_type`

is convertible to`OutputIterator's`

`value_type`

.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The associatve operator used to ‘sum’ values.`binary_op`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator `

**exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `0`

is assigned to `*result`

and the sum of `0`

and `*first`

is assigned to `*(result + 1)`

, and so on. This version of `exclusive_scan`

assumes plus as the associative operator and `0`

as the initial value. When the input and output sequences are the same, the scan is performed in-place.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `exclusive_scan`

to compute an in-place prefix sum using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::exclusive_scan(thrust::host, data, data + 6, data); // in-place scan
// data is now {0, 1, 1, 3, 5, 6}
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined. If`T`

is`OutputIterator's`

`value_type`

, then`T(0)`

is defined.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename InputIterator, typename OutputIterator> OutputIterator `

**exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `0`

is assigned to `*result`

and the sum of `0`

and `*first`

is assigned to `*(result + 1)`

, and so on. This version of `exclusive_scan`

assumes plus as the associative operator and `0`

as the initial value. When the input and output sequences are the same, the scan is performed in-place.

The following code snippet demonstrates how to use `exclusive_scan`

```
#include <thrust/scan.h>
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::exclusive_scan(data, data + 6, data); // in-place scan
// data is now {0, 1, 1, 3, 5, 6}
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined. If`T`

is`OutputIterator's`

`value_type`

, then`T(0)`

is defined.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T> _CCCL_HOST_DEVICE OutputIterator `

**exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, T init);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `init`

is assigned to `*result`

and the sum of `init`

and `*first`

is assigned to `*(result + 1)`

, and so on. This version of `exclusive_scan`

assumes plus as the associative operator but requires an initial value `init`

. When the input and output sequences are the same, the scan is performed in-place.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `exclusive_scan`

to compute an in-place prefix sum using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/scan.h>
#include <thrust/execution_policy.h>
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::exclusive_scan(thrust::host, data, data + 6, data, 4); // in-place scan
// data is now {4, 5, 5, 7, 9, 10}
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined.is convertible to`T`

`OutputIterator's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The initial value.`init`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename InputIterator, typename OutputIterator, typename T> OutputIterator `

**exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, T init);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `init`

is assigned to `*result`

and the sum of `init`

and `*first`

is assigned to `*(result + 1)`

, and so on. This version of `exclusive_scan`

assumes plus as the associative operator but requires an initial value `init`

. When the input and output sequences are the same, the scan is performed in-place.

The following code snippet demonstrates how to use `exclusive_scan`

```
#include <thrust/scan.h>
int data[6] = {1, 0, 2, 2, 1, 3};
thrust::exclusive_scan(data, data + 6, data, 4); // in-place scan
// data is now {4, 5, 5, 7, 9, 10}
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator, and if`OutputIterator`

`x`

and`y`

are objects of`OutputIterator's`

`value_type`

, then`x + y`

is defined.is convertible to`T`

`OutputIterator's`

`value_type`

.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The initial value.`init`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator `

**exclusive_scan**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `init`

is assigned to `*result`

and the value `binary_op(init, *first)`

is assigned to `*(result + 1)`

, and so on. This version of the function requires both an associative operator and an initial value `init`

. When the input and output sequences are the same, the scan is performed in-place.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `exclusive_scan`

to compute an in-place prefix sum using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
thrust::maximum<int> binary_op;
thrust::exclusive_scan(thrust::host, data, data + 10, data, 1, binary_op); // in-place scan
// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator and`OutputIterator`

`OutputIterator's`

`value_type`

is convertible to both`AssociativeOperator's`

`first_argument_type`

and`second_argument_type`

.is convertible to`T`

`OutputIterator's`

`value_type`

.is a model of Binary Function and`AssociativeOperator`

`AssociativeOperator's`

`result_type`

is convertible to`OutputIterator's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The initial value.`init`

The associatve operator used to ‘sum’ values.`binary_op`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum

### Function `exclusive_scan`

` template <typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator> OutputIterator `

**exclusive_scan**(InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op);`exclusive_scan`

computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, `init`

is assigned to `*result`

and the value `binary_op(init, *first)`

is assigned to `*(result + 1)`

, and so on. This version of the function requires both an associative operator and an initial value `init`

. When the input and output sequences are the same, the scan is performed in-place.

The following code snippet demonstrates how to use `exclusive_scan`

```
#include <thrust/scan.h>
#include <thrust/functional.h>
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
thrust::maximum<int> binary_op;
thrust::exclusive_scan(data, data + 10, data, 1, binary_op); // in-place scan
// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`OutputIterator's`

`value_type`

.is a model of Output Iterator and`OutputIterator`

`OutputIterator's`

`value_type`

is convertible to both`AssociativeOperator's`

`first_argument_type`

and`second_argument_type`

.is convertible to`T`

`OutputIterator's`

`value_type`

.is a model of Binary Function and`AssociativeOperator`

`AssociativeOperator's`

`result_type`

is convertible to`OutputIterator's`

`value_type`

.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The beginning of the output sequence.`result`

The initial value.`init`

The associatve operator used to ‘sum’ values.`binary_op`

**Preconditions**: `first`

may equal `result`

but the range `[first, last)`

and the range `[result, result + (last - first))`

shall not overlap otherwise.

**Returns**: The end of the output sequence.

**See**: https://en.cppreference.com/w/cpp/algorithm/partial_sum