累積和

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理：\(O(N)\)
クエリ：\(O(1)\)

で処理がで ...