title: Algorithm for [inclusive/exclusive]_scan in parallel <algorithm> proposal N3554
body: <p>Proposal <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3554.pdf" rel="nofollow">N3554 (A Parallel Algorithms Library)</a> for C++14, proposes (among other things), what seem to be parallel versions of the current <a href="http://www.cplusplus.com/reference/numeric/partial_sum/" rel="nofollow"><code>std::partial_sum</code></a>, e.g.:</p>
  
  <pre><code>template&lt;
      class ExecutionPolicy,
      class InputIterator,
      class OutputIterator,
      class BinaryOperation&gt;
  OutputIterator inclusive_scan(
      ExecutionPolicy &amp;&amp;exec,
      InputIterator first,
      InputIterator last,
      OutputIterator result,
      BinaryOperation binary_op);
  </code></pre>
  
  <p>With the explanation</p>
  
  <blockquote>
    <p>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 every iterator iter_j in the range [first,first + (i - result) - 1) ... The order of operands of the sum is unspecified.</p>
  </blockquote>
  
  <hr>
  
  <p>How could this operation be made parallel? It seems like, almost by definition, each output prefix_sum must be calculated for the immediate next one to be calculated - essentially leading to a serial operation.</p>
  
  <hr>
  
  <p><strong>Edit</strong> Many thanks to Aasmund Eldhuset for his answer. Personally, I found <a href="https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf" rel="nofollow">"Prefix Sums
  and Their Applications" by Guy E. Blelloch</a> to be very useful.</p>