A prefix scan computes all cumulative prefixes of a sequence under an associative operation.

For addition, the inclusive scan of

$$[3,1,4,2]$$

is

$$[3,4,8,10],$$

while the exclusive scan is

$$[0,3,4,8].$$

A naive computation of every prefix repeats work. A parallel scan instead combines values in a tree. An up-sweep computes partial reductions; a down-sweep propagates the accumulated prefix into each subtree.

A work-efficient tree scan can perform $O(n)$ total operations with $O(\log n)$ span.

Scan is more informative than a reduction: reduction keeps only the final aggregate, while scan preserves the aggregate before or through every position.

This makes scan a basic parallel primitive for tasks that initially look sequential. It can produce array offsets, compact selected elements, allocate positions for variable-size outputs, build cumulative distributions and support radix-style algorithms.

As with reductions, the combining operation must have an associative structure for regrouping to preserve the intended mathematical result.