Binary Indexed Tree(BIT)

説明

Fenwick Tree とも呼ばれる。数列 $v_1,v_2,...,v_n$ に対し, $v_i$ に値 $w$ を加える操作と $[1,a]$ の和 $v_1+v_2+...+v_a$ を求める操作をそれぞれ対数時間で行うことができるデータ構造。セグメントツリーや平衡二分探索に比べ実装が非常に単純である。

---

情報

項目	データ
計算量	$O(\log N)$

関数

BinaryIndexdTree(sz)
機能	長さ $sz$ の 0 で初期化された数列 $a$ を作成する。

add(k, x)
機能	$a_k$ に $x$ を加える。

sum(k)
機能	$a_1 + a_2 + ... + a_k$ を求める。

実装例

問題例

#	ソース	難易度
AOJ 2431 - 引越し	JAG夏合宿2012	★★★