概要

要素の更新がありうる数列について、区間和の計算が高速にできる
同様に更新ありの任意区間の区間和を高速に計算可能なSegment Treeと比較して空間計算量が半分程度
- ただしSegment Treeのように最小値などの計算に使うといったような応用力はない
Segment Treeの各nodeが表現している区間を $\lbrack l, r \rbrack$ 、そのnodeの演算結果（表現区間の区間和）を $S_{l, r}$ としたときに、 $r = j$ であるような区間のうち要素数が最大の区間の演算結果だけをBITで保持するようにする
i.e. $\mathit{BIT}\lbrack 1 \rbrack = S_{1, 1}, \mathit{BIT}\lbrack 2 \rbrack = S_{1, 2}, \mathit{BIT}\lbrack 3 \rbrack = S_{3, 3}, \mathit{BIT}\lbrack 4 \rbrack = S_{1, 4}, \dots$
ある部分和を取得したいときは区間を適切に分割するとBITに対応する値を持っているので、それらの和をとる
- 具体的には $k = k - (k\; \mathrm{AND}\; (-k))$ のように $k$ を更新していき、 $k = 0$ になるまで更新したときに出てくる値を使う（ $\mathrm{AND}$ はbit論理積演算）
  e.g. $P_{5} = \mathit{BIT}\lbrack 5 \rbrack + \mathit{BIT}\lbrack 4 \rbrack = S_{5, 5} + S_{1, 4} = S_{1, 5}$
任意の区間和を求めるときはで計算できる
- $P_{0} = \mathit{BIT}\lbrack 0 \rbrack = 0$ とする
更新時は値の変更が影響を受けるノードだけ更新する
- 具体的には全区間を $\lbrack 1, N \rbrack$ としたとき、 $k = k + (k\; \mathrm{AND}\; (-k))$ のように $k$ を更新していき、 $k \gt N$ になるまで更新したときに出てくる値を更新する
  e.g. $N = 8$ のBITで要素 $5$ を更新したとき、 $\mathit{BIT}\lbrack 5 \rbrack, \mathit{BIT}\lbrack 6 \rbrack, \mathit{BIT}\lbrack 8 \rbrack$ を更新する
上記計算の関係から数列は1-originで考えることになる
計算時間は要素の更新に $O(\mathrm{log}N)$ 、結果の取得に $O(\mathrm{log}N)$

BITを用いた代表的な計算として、 $a_{1}, \dots, a_{N}$ を昇順にバブルソートしたときに要素の交換が行われる、つまり $i \lt j$ かつ $a_{i} \gt a_{j}$ であるような $(i, j)$ の組の数（転倒数）を求めるというものがある。

$I = 0$ とする
$B = \lbrack b_{i} \mid b_{i} = \lbrack a_{i}, i \rbrack \rbrack$ とする
を昇順に安定ソートした順に、以下の操作を実行する
- $S_{j, N}$ を $I$ に加算する
- BITで表現している数列の $j$ 番目に $1$ を加算するような更新をする
$I$ を出力する