内容別リスト/高速化系/累積和 - 競技プログラミング用 知識集積所

---

雑な説明

vectorのようなデータ構造に対し、「ここからここまでの合計いくつ？」に高速に答えるためのアルゴリズム。
ただし、途中でvectorの中身は変えることはできない。
n個のデータに対しq回和を計算する場合、通常の方法でやれば計算回数がO(nq)になるところ、O(n+q)で済む。

レベル

ABCのC問題以降。

アルゴリズム内容

vectorに対し、「そこより左」または「そこまで」の和を作っておく。
例えば、{3,1,4,1,5,9,2,6}というvectorに対し、以下のように別のvectorを作る。

.at()	0	1	2	3	4	5	6	7	8
vector	3	1	4	1	5	9	2	6
「より左」の累積和	0	3	4	8	9	14	23	25	31

または

.at()	0	1	2	3	4	5	6	7
vector	3	1	4	1	5	9	2	6
「まで」の累積和	3	4	8	9	14	23	25	31

例えば前者の場合、3番目から6番目までの総和を答えたい場合、累積和の7番目から3番目を引いて25-8=17と求められる。
このvectorがどんなに長くても、最初に累積和さえ作ってしまえば区間和は引き算1回。
「L番目からR番目までの総和を答えて」というクエリが大量に飛んでくる場合などに有効。

「より左」型と「まで」型の違いは、

• 「より左」型の方が作るときにいくつか注意が必要
• 「まで」型の方が0番目からの和を取りたい場合に-1番目が存在しないケアが必要

あたり。
比較的、前者の方がバグりにくいというか、バグってるときに気づきやすい。

累積和の作り方は、いくつかの方法がある。
一番使いやすい、「より左」型の累積和の作り方。

vector<int> sum(n+1,0);
for (int i=0; i<n; i++) {
  sum.at(i+1) = sum.at(i) + a.at(i);
}

サイズが元のベクトルより1つ大きくなることに注意。
また、.at(0)に明示的に0を入れる必要があることにも注意。

同じ「より左」型でも、std関数を使う方法もある。

vector<int> sum(n+1,0);
partial_sum(a.begin(),a.end(),sum.begin()+1);

やはりサイズが1大きくなることと、.at(0)の明示的初期化が必要。
さらに、第3引数で.begin()ではなくそれに1を足す必要がある。

また、「まで型」の場合は

vector<int> sum(n);
partial_sum(a.begin(),a.end(),sum.begin());

と書けるほか、元の数列をつぶしていい場合は

for (int i=0; i<n-1; i++) {
  a.at(i+1) += a.at(i);
}

だけでも累積和にできる。
この方法は、aを作るときに0を挿入して1つ長くなった形で作ると、「より左」型にもできる。
これを知っていると、多次元累積和（未作成）を作るときに楽になる。

注意点

関連アルゴリズム

sliding window法

長さ固定の区間の和などを扱える。
種類数のように現在の状態を扱うデータが大きくなりがちなものに対しては累積和よりも有効。

尺取法

累積和と同じく条件を満たす区間を探したり個数を数えたりするアルゴリズム。
累積和と二分探索の2つが協力してO(n*logn)でやることを、あちらは1つでO(n)で処理できる。
また、種類数のように現在の状態を扱うデータが大きくなりがちなものに対しても使える。
一方で、後から「で、条件を満たす場所の和はいくつだったっけ？」と聞かれても何も答えられないのが難点。

Fenwick木（未作成）

累積和の上位互換。
同じようにそこより左の合計がすぐにわかるようになっているが、途中での値の更新もできる。

segment木（未作成）

Fenwick木の上位互換。

多次元累積和（未作成）

累積和、2次元vectorバージョン。