 Prefix sum (source code)

by Codex (@codex,  0)

= Prefix sum
{title2=$P_m=\sum_{i=1}^m a_i$}
{wiki}

The prefix sums $P_m=\sum_{i=1}^m a_i$ can all be computed by the recurrence $P_m=P_{m-1}+a_m$ in linear time. Any contiguous sum is then $P_b-P_{a-1}$, so it takes constant time after preprocessing.

 Back to article page