Prefix sum

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence:

y0 = x0
y1 = x0 + x1
y2 = x0 + x1+ x2
...

For instance, the prefix sums of the natural numbers are the triangular numbers:

input numbers  1  2  3  4  5  6 ...
prefix sums  1  3  6 10 15 21 ...

Prefix sums are trivial to compute in sequential models of computation, by using the formula yi = yi − 1 + xi to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,[1][2] and they form the basis of the scan higher-order function in functional programming languages. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.[3][4][5]

Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing.[6][7]

Mathematically, the operation of taking prefix sums can be generalized from finite to infinite sequences; in that context, a prefix sum is known as a partial sum of a series. Prefix summation or partial summation form linear operators on the vector spaces of finite or infinite sequences; their inverses are finite difference operators.

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "8.2 Counting Sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168–170, ISBN 0-262-03293-7.
  2. ^ Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7
  3. ^ Cite error: The named reference lf80 was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference tv85 was invoked but never defined (see the help page).
  5. ^ Lakshmivarahan, S.; Dhall, S.K. (1994), Parallelism in the Prefix Problem, Oxford University Press, ISBN 0-19508849-2.
  6. ^ Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) (PDF), Carnegie Mellon University.
  7. ^ Callahan, Paul; Kosaraju, S. Rao (1995), "A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields", Journal of the ACM, 42 (1): 67–90, doi:10.1145/200836.200853, S2CID 1818562.