prefix sum

Scan, or Prefix Sum

• Input
  • Array of n elements:
  • binary associate operator:
  • Identity:
• Outputs the array

C++ STL’s std::partial_sum, std::exclusive_scan, and std::inclusive_scan are example implementation of the scan algorithm. Note that the difference of partial_sum and inclusive_scan is that partial_sum additionally guarantee evaluation order.

Exclusive Vs Inclusive Scan

Exclusive: element of the result does not include element of the input

• input: [3 1 7 0 4 1 6 3]
• output: [0 3 4 11 11 15 16 22]

Inclusive

• input: [3 1 7 0 4 1 6 3]
• output: [3 4 11 11 15 16 22 25]

To generate exclusive scan from an inclusive scan, we need to shift all element in the output to right.