Scan
Scan, or Prefix Sum
- Input
- Array of n elements:
- binary associate operator:
- Identity:
- Array of n elements:
- 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
- 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.