累積和手法
概要
ある配列内の任意の区間での和を求めます。
使える状況
ある範囲のみでの部分和を何回も必要とするようなときには、この累積和手法を用いることで非常に高速に求めることが出来ます。
説明
今、例として長さのある配列の中身を次のように定義します。
これを表にすると以下のとおりです。
a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | ... | a[n-1] |
0 | 1 | 2 | 3 | 4 | 5 | ... | n-1 |
このとき、任意のについての値を求めるには、累積和を求めておくことで簡単に計算することが出来ます。
累積和とは、初めの項からの和のことをいいます。
ここで、配列の中身を次のように定義します。
つまり、はからまでの累積和であり、これを表にすると以下のとおりです。
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 |
この配列の各要素を配列の要素で書き表すと、以下のようになっています。
よって、を求めるには、
より、を計算するだけでよいことが分かります。
コード(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]; }
この部分では、累積和の配列の各要素を計算しています。
番目の累積和は、番目の累積和に番目の配列の要素を足したものであることを利用しています。
なお、ループの初めはからであることに注意する必要があります。
からにすると、のときのの値はとなってしまい、配列の添え字としては不適切なものとなってしまいます。
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]; };
この部分では、からまでの要素の和を求める関数(ラムダ式)を定義しています。
具体例
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
結果としては、
と、確かに正しく計算できていることが分かります。
なお、これらの計算はただ、をそれぞれ求めればよいのですが、そう書くよりも累積和を用いると演算回数を減らすことが出来ます。
九九表のからまでの範囲の四角形内の数字の和を求める
通常、一次元配列について考えられる累積和ですが、以下のようにして多次元配列においても指定した範囲の和を求めることが出来ます。
#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
答えとしては、
となるため、確かに正しく計算出来ていることが分かります。
このコードは、先ほどの例とは異なる部分が多いですが、これは「ただ手前の要素を引くだけだと余分なところまで引いてしまう」というところから来ています。
詳しくは、こちらの記事を参照してください。
satanic0258.hatenablog.com
紙に書いてみるとわかりやすいと思います。
備考
計算量としては、累積和の配列を初期化するのに、指定された範囲の和を求めるのにはで済みます。
この方法を用いずに、指定された範囲の和を求めようとすると毎回計算量がだけかかってしまうので、この方法はとても効率的だと言えます。
あとがき
累積和は、指定された範囲内の数値の和を求めるのにはとても役に立つ方法です。
そのため、「ある範囲内の和なら累積和だ!」と考えてしまっても良いかもしれませんね。