Prefix sum ($P_m={\sum }_{i=1}^m{a}_i$)

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.