Algorithm for [inclusive / exclusive] _scan in parallel <algorithm> proposal N3554

Proposition N3554 (Library of Parallel Algorithms) for C ++ 14, offers (among other things) what is similar to the parallel versions of the current one std::partial_sum

, for example:

template<
    class ExecutionPolicy,
    class InputIterator,
    class OutputIterator,
    class BinaryOperation>
OutputIterator inclusive_scan(
    ExecutionPolicy &&exec,
    InputIterator first,
    InputIterator last,
    OutputIterator result,
    BinaryOperation binary_op);

      

        
        
        
      

    

With an explanation

Effects: for each iterator, i in [result, result + (last-first)) performs * i = prefix_sum, where prefix_sum is the result of the corresponding sum init + * iter_0 + * iter_1 + * iter_2 + ... or binary_op (init, binary_op (* iter_0, binary_op (* iter_1, binary_op (* iter_2, ...))) for each iterator iter_j in the range [first, first + (i - result) - 1) ... The order of the sum operands is unspecified.

How can a parallel operation be performed? It looks like, almost by definition, each output of prefix_sum must be calculated for the next next calculation, which basically results in a sequential operation.

Edit Many thanks to Aasmund Eldhuset for his answer. Personally, I've found "Prefix Sums and Their Applications" by Guy E. Blelloch to be very helpful.