読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

累積和手法

アルゴリズム アルゴリズム-ら

概要

ある配列内の任意の区間での和を求めます。


使える状況

ある範囲のみでの部分和を何回も必要とするようなときには、この累積和手法を用いることで非常に高速に求めることが出来ます。


説明

今、例として長さnのある配列aの中身を次のように定義します。
a[i]=i
これを表にすると以下のとおりです。

a[0] a[1] a[2] a[3] a[4] a[5] ... a[n-1]
0 1 2 3 4 5 ... n-1


このとき、任意のi,j(i < j)についてa[i]+a[i+1]+\cdots +a[j]の値を求めるには、累積和を求めておくことで簡単に計算することが出来ます。

累積和とは、初めの項からの和のことをいいます。


ここで、配列sの中身を次のように定義します。
s[i]=a[0]+a[1]+\cdots+a[i]
つまり、s[i]a[0]からa[i]までの累積和であり、これを表にすると以下のとおりです。

s[0] s[1] s[2] s[3] s[4] s[5] ... s[n-1]
0 1 3 6 10 15 ... (n-1)n/2


この配列sの各要素を配列aの要素で書き表すと、以下のようになっています。
\begin{align}
s[0]   &= a[0]\\
s[1]   &= a[0] + a[1]\\
s[2]   &= a[0] + a[1] + a[2]\\
\cdots\\
s[i-1] &= a[0] + a[1] + a[2] + \cdots + a[i-1]\\
s[i]   &= a[0] + a[1] + a[2] + \cdots + a[i-1] + a[i]\\
\cdots\\
s[j]   &= a[0] + a[1] + a[2] + \cdots + a[i-1] + a[i] + \cdots + a[j]\\
\cdots\\
s[n-1] &= a[0] + a[1] + a[2] + \cdots + a[i-1] + a[i] + \cdots + a[j] + \cdots + a[n-1]\\
\end{align}


よって、a[i]+a[i+1]+\cdots +a[j]を求めるには、


 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s[j] = a[0] + a[1] + a[2] + \cdots + a[i-1] + a[i] + \cdots + a[j]\\
 -\underline{)\ \ \ \ \  s[i-1] = a[0] + a[1] + a[2] + \cdots + a[i-1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\\
 s[j]-s[i-1] = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,a[i] + \cdots + a[j]

より、s[j]-s[i-1]を計算するだけでよいことが分かります。


コード(C++)

//要ヘッダ:vector, algorithm
std::vector<int> a(n);
std::vector<int> s(n, a[0]);
for(int i=1; i<n; ++i){
    s[i] = s[i-1]+a[i];
}
auto partSum = [&](int l, int r) -> int {
    if(l>r) std::swap(l, r);
    if(l==0) return s[r];
    return s[r] - s[l-1];
};

コードの説明

std::vector<int> s(n, a[0]);
for(int i=1; i<n; ++i){
    s[i] = s[i-1]+a[i];
}

この部分では、累積和の配列sの各要素を計算しています。
i番目の累積和s[i]は、i-1番目の累積和にi番目の配列の要素を足したものであることを利用しています。

なお、ループの初めはi=1からであることに注意する必要があります。
i=0からにすると、i=0のときのi-1の値は-1となってしまい、配列の添え字としては不適切なものとなってしまいます。

auto partSum = [&](int l, int r) -> int {
    if(l>r) std::swap(l, r);
    if(l==0) return s[r];
    return s[r] - s[l-1];
};

この部分では、a[l]からa[r]までの要素の和を求める関数(ラムダ式)を定義しています。


具体例

2から5までの整数の和、3から9までの整数の和を求める

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

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int n=10;
    std::vector<int> a(n);
    for(int i=0; i<10; ++i){
        a[i]=i;
    }
    std::vector<int> s(n, a[0]);
    for(int i=1; i<n; ++i){
    	s[i] = s[i-1]+a[i];
    }
    auto partSum = [&](int l, int r) -> int {
        if(l>r) std::swap(l, r);
        if(l==0) return s[r];
    	return s[r] - s[l-1];
    };

    std::cout << partSum(2, 5) << "\n";
    std::cout << partSum(3, 9) << "\n";

    return 0;
}

出力

14
42

結果としては、
2+3+4+5=14
3+4+5+6+7+8+9=42
と、確かに正しく計算できていることが分かります。

なお、これらの計算はただ2+3+4+53+4+5+6+7+8+9をそれぞれ求めればよいのですが、そう書くよりも累積和を用いると演算回数を減らすことが出来ます。

九九表の3\times 3から6\times 6までの範囲の四角形内の数字の和を求める

通常、一次元配列について考えられる累積和ですが、以下のようにして多次元配列においても指定した範囲の和を求めることが出来ます。

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

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int n=9;
    std::vector<std::vector<int>> a(n+1, std::vector<int>(n+1, 0));
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=n; ++j){
            a[i][j]=i*j;
        }
    }
    std::vector<std::vector<int>> s(n+1, std::vector<int>(n+1, a[0][0]));
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
        	s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }
    auto partSum = [&](int r1, int c1, int r2, int c2) -> int {
        if(r1>r2) std::swap(r1, r2);
        if(c1>c2) std::swap(c1, c2);
        if(r1==0 && c1==0) return s[r2][c2];
        if(r1==0) return s[r2][c2] - s[r1][c1-1];
        if(c1==0) return s[r2][c2] - s[r1-1][c1];
    	return s[r2][c2] - s[r1-1][c2] - s[r2][c1-1] + s[r1-1][c1-1];
    };

    std::cout << partSum(3, 3, 6, 6) << "\n";

    return 0;
}

出力

324

答えとしては、
\ \ \ \ \ \ 9+12+15+18\\
 +12+16+20+24\\
 +15+20+25+30\\
 +18+24+30+36=324
となるため、確かに正しく計算出来ていることが分かります。

このコードは、先ほどの例とは異なる部分が多いですが、これは「ただ手前の要素を引くだけだと余分なところまで引いてしまう」というところから来ています。

詳しくは、こちらの記事を参照してください。
satanic0258.hatenablog.com

紙に書いてみるとわかりやすいと思います。
f:id:satanic0258:20160410151042p:plain


備考

計算量としては、累積和の配列を初期化するのにO(n)、指定された範囲の和を求めるのにはO(1)で済みます。

この方法を用いずに、指定された範囲の和を求めようとすると毎回計算量がO(n)だけかかってしまうので、この方法はとても効率的だと言えます。


あとがき

累積和は、指定された範囲内の数値の和を求めるのにはとても役に立つ方法です。
そのため、「ある範囲内の和なら累積和だ!」と考えてしまっても良いかもしれませんね。