先頭からの累積値をPに保存すると、任意の区間和を1回の引き算で計算できます。

累積和の構築と区間和の問い合わせシミュレーター

lとrを変えて計算を再生できます。下段は累積和配列Pです。

前計算O(n)

区間和の問い合わせO(1)

追加領域O(n)

計算式P[r+1] − P[l]

なぜ引き算1回で求められるのか

P[r+1]は位置0～rの和、P[l]は0～l−1の和です。共通部分を引くとl～rだけが残ります。Pを1要素長くしてP[0] = 0とすると、l = 0にも同じ式を使えます。

2次元累積和

S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + a[i][j]

# (r1, c1)から(r2, c2)までの長方形の和
S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]

関連するテクニック

差分配列：[l, r]にvを加える操作をd[l] += v、d[r+1] −= vで記録し、最後にdの累積和を取ります。事前にまとめて処理できる場合、各区間更新はO(1)です。

累積和とハッシュ：和がKになる部分配列はP[j] − P[i] = Kとなる組に対応します。出現済みの累積和を辞書で数えると、負数を含む入力でもO(n)で解けます。