BIT
Binary Indexed Tree (Fenwick Treeとも)
概要
数列 $ A に対して、
$ A_iに$ xを加算
$ A_1 + \cdots + A_iを得る
が$ \Omicron(\log N) でできるデータ構造
使い方
区間を更新・1点の値を得る
数列 $ A に対して、
$ A_i, \dots, A_j に$ x を加算
$ A_i を得る
も$ \Omicron(\log N) でできる
$ d_i = A_i - A_{i-1} として、$ dを BIT で管理すれば
$ d_i に$ x 、$ d_{j+1} に$ -x を加算
$ d_1 + \cdots + d_i を得る
で計算できる
区間を更新・区間の総和を得る
数列 $ A に対して、
$ A_i, \dots, A_j に$ x を加算
$ A_1 + \cdots + A_k を得る
も$ \Omicron(\log N) でできる
→ BIT 2つ使って管理
2つの数列$ p, qを用意して、
$ p_iに$ (-i+1)x、$ p_{j+1}に$ jx、$ q_iに$ x、$ q_{j+1}に$ -xを加算
$ \sum_{n=1}^{k+1} p_n + kq_nで総和を得る
で計算できる
導出過程
区間$ [i,j] に$ x を足したとき、$ [1, k) の総和$ S(k) は、
$ k < i のとき、$ S(k) = 0
$ i \le k \le j のとき、 $ S(k) = (k - i + 1) x = (- i + 1)x + kx
$ j < k のとき、$ S(k) = (j - i + 1) x
だけ増える。
$ S(k) = \sum p_n + k \sum q_n と表すことを考えると、
$ \sum p_n : $ k \lt i で$ 0 、$ i \le k \le j で$ (-i+1)x 、$ j \lt k で$ (j - i + 1) x
$ \sum q_n : $ k \lt i で$ 0 、$ i \le k \le j で$ x 、$ j \lt k で $ 0
としたいので、$ p_iに$ (-i+1)x、$ p_{j+1}に$ jx、$ q_iに$ x、$ q_{j+1}に$ -xを加算すればうまくいく。
転倒数
転倒数 $ \mathrm{inv}(A) \coloneqq \#\{(A_i, A_j)|i < j \land A_i>A_j\}
→ BIT をカウンター的に使って、$ b_i \coloneqq iの出現数、$ \sum b_i = i以下の出現数として計算する。
問題