フェニック木 (Fenwick tree) とも呼ばれます．
基本形（区間和）
機能
数列$a_{1},a_{2},...,a_{N}$があったとき，add(i, x)：$(i,x)$を与えて$a_{i} + x$を計算する．get(i)：$i$を与えて$a_{1} + a_{2} + \cdots + a_{i}$を計算する．
実装例
bit[i]=$\displaystyle \sum_{k = i}^{i + (i \& -i)} a_{i}$ (1-indexed)
bit_size = N + 1 bit = [0] * bit_size def add(i, x): i += 1 # iとして0-indexedの量を渡す場合 while i < bit_size: bit[i] += x i += i & -i def get(i): ans = 0 i += 1 # iとして0-indexedの量を渡す場合 while i > 0: ans += bit[i] i -= i & -i return ans
例題
応用（最大・最小・XORなど）
機能
数列$a_{1},a_{2},...,a_{N}$があったとき，update(i, x)：$(i,x)$を与えて$a_{i}$を$x$に置き換える．get(i)：$i$を与えて$f(a_{1}, a_{2} , ..., a_{i})$を計算する．
実装例
$f = \max $の場合．INF = 1 << 60 bit_size = N + 1 bit = [0] * bit_size def update(i, x): i += 1 while i < bit_size: bit[i] = max(bit[i], x) i += i & -i def get(i): ans = - INF i += 1 while i > 0: ans = max(ans, bit[i]) i -= i & -i return ans
例題
応用（二分探索→ある要素が何番目に大きいかがわかる）
「基本形」に以下の関数（二分探索）を追加する．$x$を与えたとき，$ x \leq a_{1} + a_{2} + \cdots + a_{i}$となる最小の$i$（と，その1ステップ前の累積和）を返す．
def lower_bound(x): """ 累積和がx以上になる最小のindexと、その直前までの累積和 """ depth = N.bit_length() pos, acc = 0, 0 for i in range(depth, -1, -1): k = pos + (1 << i) if k <= N and acc + bit[k] < x: acc += bit[k] pos += 1 << i return pos + 1, acc
【参考】
【例題】
