The scan operation, also termed "parallel prefix sum", takes in a vector (stream) of data elements and an (arbitrary) associative binary function '+' with an identity element 'i'. If the input is a1, a2, a3, ..., an "exclusive scan" produces the output a0, a0 + a1, a0 + a1 + a2, ..., while an "inclusive scan" produces the output a0 + a1, a0 + a1 + a2, a0 + a1 + a2 + a3, ... and does not require an identity to exist. While at first glance the operation may seem inherently serial, efficient parallel scan algorithms are possible and have been implemented on graphics processing units. The scan operation has uses in e.g., quicksort and sparse matrix-vector multiplication.