蟻本3-3「さまざまなデータ構造を操ろう」の区間加算可能なBinary Indexed Treeを行間埋めしました.

問題

数列$A_1,A_2,...,A_N$と$Q$個のクエリが与えられます．クエリを順次処理してください．クエリは次の2種類です．

$l,r,x$が与えられるので，区間$A_l,A_{l+1},...,A_r$に$x$を加える．
$l,r$が与えられるので，区間$A_l,A_{l+1},...,A_r$の和を求める．

解法

２つのBinary Indexed Tree(BIT)を用意すると高速に処理することができます．

Binary Indexed Treeとは

以下の記事がわかりやすかったです

BITの特徴をまとめると，

1要素$A_i$に$x$を加える操作は高速（$O(\log n)$）
区間$A_1,A_2,...,A_r$の和算出も高速（$O(\log n)$）
- 区間$[l,r]$の和は$\sum_{k=1}^{r}a_k - \sum_{k=1}^{l-1}a_k$で
ただし，区間$A_l,A_{l+1},...,A_r$に$x$を加える操作は苦手
- BITを２つ組み合わせると高速に処理できる（$O(\log n)$）

”区間に値を加える”とは

準備

数列$A_1,A_2,...,A_N$の区間$[l,r]$に$x$を加算した数列を，$A'_1,A'_2,...,A'_N$と書きます．つまり

A'_i = 
\begin{cases}
A_i+x & \text{if $ l \le i \lt r+1 $,} \\
A_i & \text{otherwise}.
\end{cases}

また，$s(i),s'(i)$を以下のように定義します．

$s(i)=\sum_{k=1}^{i}A_k$ （加算前の和）
$s'(i)=\sum_{k=1}^{i}A'_k$ （加算後の和）

すると，$s(i)$と$s'(i)$の関係は

$1 \le i \lt l$のとき
$$ s'(i)=s(i) $$
$l \le i \lt r+1$のとき
$$ s'(i)=s(i)+x(i-l+1) $$
$r+1 \le i \le N$のとき
$$ s'(i)=s(i)+x(r-l+1) $$

となります．$s(i)$を左辺に移項するとこのようなグラフになります．

このグラフのような$s(i)\rightarrow s'(i)$の更新を高速に行うことが目標です．

2つのBITで和を表す

２つのBIT（BIT0とBIT1とします）を用意して，次のように値を管理するとうまくいきます．

$s(i)$ =（BIT0の1～i要素の和）+ $i$ ×（BIT1の1~i要素の和）

BITは内部で数列の情報を保持し，1要素加算と区間和取得を高速に行うことができるデータ構造でしたので，BIT0，BIT1もそれぞれ内部で数列の情報を保持しています．
BIT0が保持している数列を$a_1,a_2,...,a_N$とします．すなわち

（BIT0の1～i要素の和）= $\sum_{k=1}^{i}a_k$

です．同様にBIT1が保持している数列を数列$b_1,b_2,...,b_N$とおくと，$s(i)$は次のように書けます．

s(i)= \sum_{k=1}^{i}a_k + i \sum_{k=1}^{i}b_k

$s(i)$を更新して$s'(i)$とした後の，BIT0とBIT1の保持している数列をそれぞれ$a'_i,b'_i$と書くと，

s'(i)= \sum_{k=1}^{i}a'_k + i \sum_{k=1}^{i}b'_k

なので

s'(i)-s(i)= \sum_{k=1}^{i}(a'_k-a_k) + i \sum_{k=1}^{i}(b'_k-b_k)

と書けます．

2つのBITの更新方法

「$s'(i)-s(i)$」を2つのBITに割り振ります．

BIT1： $l$から$r$にかけての傾き部分（図の(b)）
BIT0：上記以外（図の(a)）

BIT0

BIT0で管理している数列の和(a)から$\Sigma$を取り除くと(a)'のようになります．

(a)'の$a'_i-a_i$はBIT0で管理している数列$a_i$の更新前後の差なので，これがそのままBIT0への加算量になります．つまり，

BIT0の$l$個目の要素に$-x(l-1)$を加算
BIT0の$r+1$個目の要素に$xr$を加算

です．BITの得意な1要素への加算に落とし込むことができました．

BIT1

BIT1の和には$i$が掛けてあったので，まず$i$を取り除いて(b)'とします．さらに$\Sigma$を取り除くと(b)''になります．

(b)''から，BIT1も次のような1要素への加算に落とし込むことができました．

BIT1の$l$個目の要素に$x$を加算
BIT1の$r+1$個目の要素に$-x$を加算

BIT0,BOT1の操作をまとめると

区間$A_l,A_{l+1},...,A_r$に$x$を加える操作は，次の4つの「BITを用いた数列の1要素への加算」で表すことができます．

BIT0の$l$個目の要素に$-x(l-1)$を加算
BIT1の$l$個目の要素に$x$を加算
BIT0の$r+1$個目の要素に$xr$を加算
BIT1の$r+1$個目の要素に$-x$を加算

和の求め方

数列$A_1,A_2,...,A_N$の$i$要素目までの和は，$s(i)$の定義をそのまま利用して次のように求めます．

$s(i)$ =（BIT0の1～i要素の和）+ $i$ ×（BIT1の1~i要素の和）

実装例

冒頭のリンクの先を参照してください．

終わりに

蟻本は一目見ると説明不足に感じますが，後で読み直すと必要十分な説明になっていますね．