累積和 - NOSSの競プロメモ

累積和

ある領域の総和を$ O(1)で求める。前処理$ O(N)

$ sum(i)= \sum_{i=0}^{N-1} a_i

とすれば、区間[L, R)の和は$ sum(R) - sum(L)

更新には$ O(N)かかるので更新が多い場合はSegment木を用いたほうが効率的。