累積和

累積和

区間に含まれる特定の個数を高速に求める方法をAtCoderで学びました。累積和と呼ばれるアルゴリズムのようです。 理解したことを整理しておきます。

AtCoderでの問題は以下です。 https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

簡略化のために、以下の問題設定とします。

  • 以下の図1の数列  {a_n} が与えられる。
  •  a_i (1 \leq i \leq 10) は  a_i = 0 または 1 の値を取る。
  • 任意の l から r区間に含まれる  a_i = 1 の数を集計する。  (1 \leq l \leq r \leq 10)

図1

 a_1  a_2  a_3  a_4  a_5  a_6  a_7  a_8  a_9  a_{10}
 0  1  1  0  1  0  1  1  1  0

愚直な解き方

a_l から a_r までをループして、 a_i = 1 のとき、集計結果(resultとします)を +1 する という解き方が考えられます。 たとえば、  l = 3, r = 7 とすると、resultは 3 になります。

 a_i0 または 1 なのかを調べることを判定と呼ぶことにします。 この手法だとresultを x 回計算しないといけないときに、(r - l + 1) * x 回の判定が必要になります。 同じ区間を何度もループすることになるので無駄が多いです。

効率的な解き方

累積和という方法を使用するとこの問題を効率的に解くことができます。 累積和では、まずあらかじめ 1 から i までの和 s_i = \sum_{k=1}^i a_k を求めておきます。

求めた結果は以下のようになります。

 s_1  s_2  s_3  s_4  s_5  s_6  s_7  s_8  s_9  s_{10}
0 1 2 2 3 3 4 5 6 6

s_i を求めておけば、区間  l, r におけるresultは  s_r - s_{l-1} で求めることができます。
 l = 3, r = 7 とすると、resultは  s_7 - s_{2} = 4 - 1 = 3 になります。  l = r の場合でも同様です。
例えば、 l = 6, r = 6 とすると、resultは  s_6 - s_5 = 3 - 3 = 0 になります。
 l = 7, r = 7 とすると、resultは  s_7 - s_6 = 4 - 3 = 1 になります。

なぜこの方法で求められるかをまとめておきました。数列  {a_n} を以下のように考えます。

 a_1, a_2, \cdots, a_{l-1}, a_{l}, a_{l+1}, \cdots, a_{r-1}, a_{r}, a_{r+1}, \cdots, a_n

求めたいのは  a_{l}, \cdots, a_{r} にある a_{i} = 1 の個数でした。 これは次のように言い換えることができます。

 a_{1}, \cdots, a_{r} にある a_{i} = 1 の個数から、 a_{1}, \cdots, a_{l-1} にある a_{i} = 1 の個数を引いたもの」です。

 a_{1}, \cdots, a_{r} にある a_{i} = 1 の個数は  s_{r}によって、
また  a_{1}, \cdots, a_{l-1} にある a_{i} = 1 の個数は  s_{l-1}で求めているため、  s_{r} - s_{l-1} で求められたということになります。事前に  s_{i} を求めておけば、区間の個数集計は  O(1) の計算量で求められることになります。 すなわち、resultを x 回計算しないといけないときに、高々 x 回の判定で求められることになり、効率的なことが分かります。

累積和が適応できそうなAtCoderの問題たち

https://beta.atcoder.jp/contests/abc084/tasks/abc084_d https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

リンク集

累積和の理解に役に立ちそうなリンク集を載せておきます。
累積和とその逆演算の一般化 - antaの競技プログラミング練習日記
累積和手法 - sataniC++