累積和を解説

はじめに

　本記事では、競技プログラミング初心者向けに累積和の使い方を解説します。累積和はABCのC問題くらいから必要になる知識なので、AtCoderを始めた人はぜひ知っておきましょう。
　この記事では前半で累積和の考え方について説明した後、後半ではABC037C問題を例題に実際にコードを書いて累積和を使ってみようと思います。

累積和を使ってできること

　長さ$n$の数列$ a_0, a_1, a_2, \ldots, a_{n-1} $のある区間の和を求めたい時どれくらいの回数の足し算が必要になるでしょうか。例えば、$a_3$から$a_{10}$までの和（ただし$10<n$）を求める場合$7$回の足し算が必要です。一般的に、$a_s$から$a_t$までの和（ただし$s \leqq t < n$）を求めるためには、$t-s$回の足し算が必要になります。累積和を使用すると、適切な前処理を行うことで数列の任意の区間の和を定数時間で（つまり非常に高速で）求めることができます。

累積和の考え方

前処理

　数列$ a_0, a_1, a_2, \ldots, a_{n-1} $の任意の区間の和を高速で求めるため、数列$ b_0, b_1, b_2, \ldots, b_{n-1}, b_n $を次のように定義します。

\begin{align}
b_0 &= 0 \\
b_i &= \sum_{j=0}^{i-1} a_j \ (i=1,2,3,\cdots, n-1,n) \\
&= b_{i-1} + a_{i-1}  \\
\end{align}

　数列$\lbrace b_i \rbrace$の値を求めるために必要な足し算の回数は$n$回です。

区間和の計算

　$\lbrace b_i \rbrace$を用いて$\lbrace a_i \rbrace$の$[s,t)$における和を求めます。ただし$[s,t)$は、$s$以上$t$未満の区間を表します。

\begin{align}
\sum_{i=s}^{t-1}a_i &= \sum_{i=0}^{t-1}a_i - \sum_{i=0}^{s-1}a_i \\
&= b_t - b_s \\
\end{align}

　一回の引き算で$\sum_{i=s}^{t-1}a_i$の値が求まるため非常に高速です。

使用例

ABC037C問題を累積和を使って解きます。

program.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
typedef vector<LL> VLL;

int main(void) {
    //入力
    LL n, k;
    cin >> n >> k;
    VLL a(n);
    for (LL i = 0; i < n; i++) {
        cin >> a[i];
    }

    //累積和の前処理
    //b[i] = a[0] + a[1] + … + a[i-1]
    VLL b;
    b.push_back(0);
    for (LL i = 0; i < n; i++) {
        b.push_back(b[i] + a[i]);
    }

    //出力する値を計算
    LL sum = 0;
    for (LL i = 0; i < n - k + 1; i++) {
        sum += b[i + k] - b[i];
    }

    //出力
    cout << sum << endl;

    return 0;
}

最後に

　分かりにくい箇所も多々あるかと思いますので質問や提案等を頂ければできる限り改善していきたいと思っています。ご覧いただきありがとうございました。