English Wikipedia - The Free Encycl...
Download this dictionary
Prefix sum
In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers is a second sequence of numbers , 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 sequential models of computation, by using the formula 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, and they form the basis of the scan higher-order function in functional programming languages. When datasets are stored in Fenwick trees, prefix sums can be calculated in O(log) time. Prefix sums of large datasets can be computed in using Fenwick tree. 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.

See more at Wikipedia.org...


© This article uses material from Wikipedia® and is licensed under the GNU Free Documentation License and under the Creative Commons Attribution-ShareAlike License