BIT(Binary-Indexed-Tree)
説明
Fenwick Tree とも呼ばれる。数列に対し, ある要素に値を加える操作と, 区間和を求める操作をそれぞれ対数時間で行うことが出来るデータ構造。セグメント木や平衡二分探索木に比べ実装が非常に単純で, 定数倍も軽い。
使い方
- $\mathrm{sum}(k)$: 区間 $[0, k]$ の合計を求める(閉区間なので注意)
- $\mathrm{add}(k, x)$: 要素 $k$ に値 $x$ を加える
計算量
$O(\log N)$
実装例
応用: BIT上の二分探索
$\sum_{i=0}^{k} a_k \ge w$ となる最小の $k$ を求めたい(std::lower_bound() のイメージ)とき, BIT上を二分探索することで $O(\log N)$ 時間で行うことができる。