= Prefix sum
{title2=$P_m=\sum_{i=1}^m a_i$}
{wiki}
A prefix sum stores the accumulated <sum> through a specified position in a finite <sequence> or <array>. For inputs $a_1,\ldots,a_n$, include the <empty sum> $P_0=0$ and set
$$
P_m=\sum_{i=1}^m a_i,\qquad P_m=P_{m-1}+a_m\quad(1\leq m\leq n).
$$
For the original input $(4,-2,5,-1,3,-4)$, the prefix array including $P_0$ is $(0,4,2,7,6,9,5)$. A negative entry makes the accumulated <sum> decrease; a prefix sum does not have to be monotone. Conversely, the original entry is recovered by <subtraction>: $a_m=P_m-P_{m-1}$.
The useful cancellation is that any contiguous block has <sum>
$$
\boxed{\sum_{i=\ell}^r a_i=P_r-P_{\ell-1}\qquad(1\leq\ell\leq r\leq n).}
$$
Both prefixes include the entries before $\ell$; subtracting cancels those entries. In the example, the <sum> from positions two through four is $-2+5-1=2$, recovered as $P_4-P_1=6-4$. The <arithmetic mean> of that block is $2/3$, obtained by dividing its <sum> by its length. Prefix sums therefore make many repeated questions about an unchanged <array> cheap: reuse accumulated totals instead of resumming every block.
\Image[/prefix-sum-range-cancellation.png]
{title=Two <prefix sums> recover a contiguous block by <subtraction>}
{description=The original six-entry <array> has negative as well as positive values. Highlighted entries two through four sum to two. Their accumulated endpoint values are $P_1=4$ and $P_4=6$, so $P_4-P_1=2$. The initial $P_0=0$ also handles a block beginning at the first entry without a separate arithmetic rule.}
The sequential recurrence builds all $n+1$ prefixes in $O(n)$ <time complexity> and storage; each block query needs two reads and one <subtraction>, hence $O(1)$ <time complexity>. These counts assume constant-cost arithmetic and access to <array> entries. If one input changes, all later stored prefixes change, so this simple representation is most useful when queries outnumber updates. For <integer> inputs, sufficient numeric capacity must be retained; with <floating-point arithmetic>, subtracting large nearby prefixes can lose relative accuracy for a small block total. The exact mathematical identity does not eliminate representation error.
The apparently sequential recurrence also motivates a <prefix scan>: <associativity> permits a tree of partial calculations that yields all accumulated results in parallel. Guy E. Blelloch's 1990 technical report systematically develops this operation and its applications; its authored chapter version explains the two tree sweeps used to obtain all prefixes. https://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/CMU-CS-90-190.html[Blelloch, Prefix Sums and Their Applications, CMU-CS-90-190, November 1990]{ref}. https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf[Blelloch, authored chapter version, §§1.1–1.2: sequential scans and parallel tree sweeps]{ref}.
Back to article page
