累積和
累積和
区間に含まれる特定の個数を高速に求める方法をAtCoderで学びました。累積和と呼ばれるアルゴリズムのようです。 理解したことを整理しておきます。
AtCoderでの問題は以下です。 https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
簡略化のために、以下の問題設定とします。
- 以下の図1の数列 が与えられる。
- は または の値を取る。
- 任意の から の区間に含まれる の数を集計する。
図1
愚直な解き方
から までをループして、 のとき、集計結果(resultとします)を する という解き方が考えられます。 たとえば、 とすると、resultは になります。
が または なのかを調べることを判定と呼ぶことにします。 この手法だとresultを 回計算しないといけないときに、 回の判定が必要になります。 同じ区間を何度もループすることになるので無駄が多いです。
効率的な解き方
累積和という方法を使用するとこの問題を効率的に解くことができます。 累積和では、まずあらかじめ から までの和 を求めておきます。
求めた結果は以下のようになります。
を求めておけば、区間 におけるresultは で求めることができます。
とすると、resultは になります。
の場合でも同様です。
例えば、 とすると、resultは になります。
とすると、resultは になります。
なぜこの方法で求められるかをまとめておきました。数列 を以下のように考えます。
求めたいのは にある の個数でした。 これは次のように言い換えることができます。
「 にある の個数から、 にある の個数を引いたもの」です。
にある の個数は によって、
また にある の個数は で求めているため、
で求められたということになります。事前に を求めておけば、区間の個数集計は の計算量で求められることになります。
すなわち、resultを 回計算しないといけないときに、高々 回の判定で求められることになり、効率的なことが分かります。
累積和が適応できそうなAtCoderの問題たち
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d https://beta.atcoder.jp/contests/abc089/tasks/abc089_d
リンク集
累積和の理解に役に立ちそうなリンク集を載せておきます。
累積和とその逆演算の一般化 - antaの競技プログラミング練習日記
累積和手法 - sataniC++