区間加算Binary Indexed Tree

[蟻本](https://www.amazon.co.jp/dp/B00CY9256C)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とは
以下の記事がわかりやすかったです

* [Binary indexed tree](https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree)
* [Binary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまで](https://algo-logic.info/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$と書きます．つまり

```math
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)$を左辺に移項するとこのようなグラフになります．

![1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/481254/914ec6be-8beb-3393-0dcf-c95c7999e150.png)

このグラフのような$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)$は次のように書けます．

```math
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$と書くと，

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

なので

```math
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)）

![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/481254/39743c81-74f6-b41c-8aad-9aa06bc2ebb2.png)

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

![3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/481254/731ffcbc-3365-da87-272e-c8cd6ddcf169.png)

(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)''になります．

![4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/481254/3a0510ec-8c1e-1ef0-0545-e4a0188b24b9.png)

(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要素の和）


### 実装例
[冒頭のリンク](#binary-indexed-treeとは)の先を参照してください．

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