累積和

コード例

A = [3, 1, 4, 1, 5, 9]
S = [0]
for x in A:
    S.append(S[-1] + x)

L = 0
R = 3
print(S[R] - S[L]) # 8

配列AのL以上R未満の合計値を計算する。

累積和とは、データ列の先頭から各要素までの和を、あらかじめ計算して記録しておく手法のこと。この計算結果を保持する配列を「累積和配列」と呼ぶ。

身近な例で言えば、毎月の売上データがあったときに「第3月までの累計売上」「第4月までの累計売上」のように、ある時点までの合計値を次々と計算していくイメージ。

この「累計」をあらかじめ用意しておくことで、特定の区間の合計値を驚くほど高速に計算できるようになる。

累積和の最大のメリットは、指定された区間の合計値を、一瞬（O(1)）で計算できること。

例えば、A = [3, 1, 4, 1, 5, 9] という配列があり、「インデックス2から4までの合計は？」と聞かれたとする。

素朴な方法: A[2] + A[3] + A[4] = 4 + 1 + 5 = 10 のように、毎回ループを回して足し合わせる。区間が長くなると、その分計算時間も長くなる。
累積和を使う方法: 事前に作った累積和配列を使えば、たった1回の引き算 S[5] - S[2] で 10 という答えを得られる。区間の長さに関係なく、計算時間は常に同じになる。

何度も区間和を計算する必要がある問題では、この差は非常に大きくなる。

累積和配列 S を作る手順はとてもシンプルで、元の配列を A とする。

累積和配列 S があれば、区間 [L, R) (インデックスLからR-1まで) の合計値は、次の式で求められる。

区間和 = S[R] - S[L]

なぜこれで計算できるのか見てみる。

この2つを引き算すると、A[0]からA[L-1]までの部分がごっそり相殺され、A[L]からA[R-1]までの和だけが残る。

A = [3, 1, 4, 1, 5, 9] において、インデックス L=2 から R=5 未満（つまりA[2], A[3], A[4]）の合計値を求めてみる。

よって、区間和は S[5] - S[2] = 14 - 4 = 10 となる。実際に A[2] + A[3] + A[4] = 4 + 1 + 5 = 10 なので、正しく計算できていることがわかる。