
累積和で区間の合計を求める
解き方
累積和は、配列の先頭から各位置までの合計を別の配列に保持する方法です。同じ配列について、さまざまな区間の合計を繰り返し求めるときに使えます。ここでは要素番号を1から数え、補助配列Sの0番目を0と定めます。
手順を追う例
A=[3, 1, 4, 2]に対し、S[0]=0、S[i]=S[i−1]+A[i] とすると、Sは[0, 3, 4, 8, 10]です。l番目からr番目までの合計はS[r]−S[l−1]で求めます。rまでの合計から、区間の手前までの合計を引きます。
確認問題【オリジナル】
A=[2, 5, 1, 6, 3]のとき、2番目から4番目までの合計を累積和で求めてください。S[4]−S[2]ではなぜ正しくありませんか。
答えと解説
Sは[0, 2, 7, 8, 14, 17]です。答えはS[4]−S[1]=14−2=12。S[4]−S[2]では2番目の5まで引いてしまい、3番目と4番目の合計7になります。累積和を作る処理は要素数nに比例し、作成後の各区間の合計は配列の2か所を読むだけで計算できます。