累積和

累積和とは配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速に行うことができます。

配列と累積和

int型の配列があり、そのなかから連続する K 個の整数の和の最大値を計算しなければならないときに重宝します。

二次元累積和

二次元配列でも同じようなことをやってみることにします。

二次元配列の累積和は以下のように考えます。

これは以下の方法で計算できます。

一番上を0行目、一番左を0列目とすると、上から1行目、左から2列目を起点に幅3、高さ2であれば赤で囲われている部分から青と緑の部分を引きます。これだと二重に引いてしまった部分があるのでその部分を足します。計算式は 195-15-69+3 となり 114 が答えです。これは表示されている内容と一致しています。

二次元配列の連続する和の最大値

では二次元配列の累積和をつかって幅3、高さ2の連続する部分の和で最大のものを求めてみることにします。最大値は174になります。

実行結果

いもす法

いもす法は累積和を応用したアルゴリズムです。

配列といもす法

配列の連続する領域に同じ値を加算する処理ではいもす法で処理時間を短縮することができます。店内にどれだけお客さんがいるかを考えてみることにします。時間の経過とともにお客様は来たり帰ったりを繰り返します。

上の例では時間を表わす配列のサイズは10と小さく、店に出入りする時間の幅も小さいので、処理に時間がかかりすぎることはありません。しかし、実際には時間を表わす配列のサイズはもっと大きく、店に出入りする時間の幅も大きい場合はどうなるでしょうか?

いもす法とは、区間の入口と出口で要素分の加算・減算を行ない累積和を求める方法です。この方法だと配列のある区間内の値を何度も書き換える必要がなくなるので、処理の高速化が期待できます。

当然のことながら実行結果は同じになります。

二次元上のいもす法

二次元上のいもす法は、区間の入口と出口を以下のように設定します。ここでは [2, 2]から[4, 5] まで 2を加算し、[4, 4]から[6, 7] まで 3を加算する処理をおこなっています。

(参考)【paizaラーニング】累積和応用編