In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers {math|x0, x1, x2, ...} is a second sequence of numbers {math|y0, y1, y2, ...}, the sums of prefixes (running totals) of the input sequence: For instance, the prefix sums of the natural numbers are the triangular numbers: Prefix sums are trivial to compute in sequ...