累積和

概要

配列上の「ここからここまでの合計はいくつ？」に高速に答えるためのアルゴリズム。
ただし、途中で配列の中身は変えることはできない。

$N$ 個のデータに対し $Q$ 回和を計算する場合、通常の方法でやれば計算回数が $O(NQ)$ になる。
しかし、このアルゴリズムを用いれば、$O(N+Q)$ で済む。

アルゴリズム内容

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

または

例えば前者の場合、A[3] から A[6] までの総和を答えたい場合を考える。
この場合、「より左」の累積和の sum[7] から sum[3] を引いて $25-8=17$ と求められる。
「まで」の方を用いるなら、sum[6] から sum[2] を引いてやはり $25-8=17$ となる。

この配列がどんなに長くても、最初に累積和さえ作ってしまえば区間和は引き算 $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$ つ大きくなることに注意。
また、sum[0] に明示的に 0 を入れる必要があることにも注意。

同じ「より左」型でも、標準ライブラリを使う方法もある。

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

やはりサイズが $1$ 大きくなることと、sum[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$ つ長くなった形で作ると、「より左」型にもできる。
これを知っていると、二次元累積和（あるいはそれ以上の次元）を作るときに楽になる。

実際に区間和を求めるときは、以下のようになる。

※ 「まで」型の場合、$l=0$ のときは分岐処理で sum.at(l-1) を引かないようにする。

使い方の応用

逆演算が存在する他の演算でも使える

和だけでなく、逆の演算が存在すれば、なんでも同様の処理ができる。

逆演算が存在しない演算でも部分的に使える

逆の演算が存在しない場合も、部分的には同様の処理ができる。

その他、累積最大公約数、累積最小公倍数、累積OR、累積ANDなども可能（いずれも逆演算はない）。

逆演算が存在しない場合は、開始地点の自由な指定はできないが、端からのデータは使用できる。
例えば、自身以外の最大値を求める場合は、左右それぞれからの累積最大値を用いることができる。
$i$ 番目以外の最大値を知りたければ、左から $i-1$ 番目までと右から $i+1$ 番目までの大きい方を求める。

たくさんの範囲で、条件を満たすものの個数を数える

ある条件（毎回同じ）を満たす個数が、配列内の指定区間にいくつあるかを求めるのにも利用できる。
具体的には、条件を満たすところは 1、そうでないところは 0 にした配列を用意し、その累積和を作る。
区間和がそのまま、範囲内で条件を満たす個数となる。

注意点

オーバーフローに注意

たくさんの値の和を取るので、オーバーフローしやすい。
最大サイズですべて最大値だった場合に最後の値がいくつになるか、事前に確認することが必要。

何も考えずに整数は全部 long long 型にすれば事故が起こりにくくすることはできる。
しかし、それすらはみ出る場合もあるため根本対策にはなっていない。
事故が減るメリットよりも、確認の癖がつきにくいデメリットの方が大きいかもしれない。

また、partial_sum はもとの配列と同じ型で和を取っていく。
A を vector<int> で作ると、sum だけ vector<long long> にしてもオーバーフロー対策にならない。
この場合は A 自体を vector<long long> にしなければならない。

配列の中身は後から変えられない

中身に変更がある場合、$1$ つ変更するたびに累積和が全て作り直しになる。
変わるたびに作り直して間に合うならいいが、ダメな場合はFenwick木やsegment木を用いる。

区間データが大きい場合には使えない

また、数値の種類数のように $1$ 箇所ごとのデータを詳細に持って大きくなってしまう場合は使えない。
sliding window法や尺取法、その他問題に対応できるアルゴリズムを用いること。

関連アルゴリズム

sliding window法

長さ固定の区間を順に調べる処理を扱える。
種類数のように現在の状態を扱うデータが大きくなりがちなものに対しても使える場合がある。
一方で、後から改めて任意区間の処理を求められても何も答えられないのが難点。

尺取法

累積和と同じく、条件を満たす区間を探したり個数を数えたりするアルゴリズム。
累積和と二分探索の $2$ つが協力して $O(N\log N)$ でやることを、尺取法は $1$ つで $O(N)$ で処理できる。
sliding window法の長さ可変バージョンであり、累積和と比較した長所短所もほぼ同じ。

Fenwick木

累積和の上位互換。
同じように任意の区間の和がすぐにわかるようになっているが、途中での値の更新もできる。

segment木

Fenwick木のさらに上位互換。
やはり、任意の区間の和がすぐにわかるようになっているが、途中での値の更新もできる。
逆演算を利用しないので、累積最大値なども任意区間で求められる。

lazy segment木

segment木のさらに上位互換。
区間にまとめて代入とか、そういうことまでできるようになっている。

階差数列

累積和の逆。
階差数列の方をうまく処理し、累積和の方に真にほしいデータが出現するようにする。

二次元累積和

累積和、二次元配列バージョン。

動的計画法

あまり意識することはないが、実は累積和は動的計画法の一種である。