Prefix Sum

The prefix sum, cumulative sum, or simply scan of a sequence of numbers \(x_0, x_1, x_2, …\) is a second sequence of numbers \(y_0, y_1, y_2, …\), the sums of prefixes (running totals) of the input sequence, e.g., \(y_2 = x_0 + x_1 + x_2\). Prefix sums are trivially computable as \(y_i = y_{i-1} + x_i\). Prefix sum may be generalized to any binary operation, e.g., using multiplication instead of addition generates the sequence of factorial numbers instead of triangular numbers.

An inclusive scan includes input \(x_i\) when computing output \(y_i\), while an exclusive scan does not. Exclusive scans may accept a separate “\(x_{-1}\)” value with which to seed the scan. Some languages offer scan functions, e.g., C++’s std::inclusive_scan and std::exclusive_scan.