Scan

Scan, or Prefix Sum

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.