A prefix scan computes successive accumulated results for an associative operation 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 and both have successive minima , 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.
New to topics? Read the docs here!