累積和

区間に含まれる特定の個数を高速に求める方法を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_i$ が $0$ または $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$ 回の判定で求められることになり、効率的なことが分かります。