累積和
ある領域の総和を
$ O(1)
で求める。前処理
$ O(N)
$ sum(i)= \sum_{i=0}^{N-1} a_i
とすれば、区間[L, R)の和は
$ sum(R) - sum(L)
更新には
$ O(N)
かかるので更新が多い場合は
Segment木
を用いたほうが効率的。
#区間