Prefix sums

Pay once up front, then answer any range total with one subtraction.