= Prefix scan
{title2=$s_m=a_1\mathbin\oplus\cdots\mathbin\oplus a_m$}
A prefix scan computes successive accumulated results for an <associative operation> $\oplus$ while keeping input order fixed. A scan based on <addition> produces <prefix sums>; one based on <matrix multiplication> produces successive ordered matrix products. <Associativity> allows regrouping, while <commutativity> is unnecessary because the order stays fixed. If an initial empty prefix is included, its value is the <identity element> for the chosen operation.
The ability to compute accumulated results does not by itself allow subtraction of two prefixes. For example, two accumulated minima cannot reveal a block minimum: the lists $(1,7,8)$ and $(1,2,3)$ both have successive minima $(1,1,1)$, but the minimum of positions two through three is seven for one and two for the other. Prefix sums support block recovery because <addition> has <additive inverses>; an arbitrary <associative operation> need not have that property.
Back to article page
