Binary Indexed Tree (BIT)

蟻本 p.159

https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree

概要

Binary Indexed Tree (BIT) または Fenwick Tree は、累積和に更新操作を加えたデータ構造。

セグメント木の機能を削り、実装を単純化したものともみなせる。

\(n\) 個の要素について、次の操作を行うことができる。

• 初期化: \(\mathcal{O}(n)\)

• 要素1つに対する加算: \(\mathcal{O}(\log{n})\)

• 部分和を求める問い合わせ: \(\mathcal{O}(\log{n})\)

部分和では区間 \([1, r]\) の和が求まる。

任意の区間 \([l, r]\) の和を求めるには、累積和と同様に \([1, r]\) の部分和から \([1, l-1]\) の部分和を引けばよい。

原理

BITの加算操作・更新操作ではセグメント木と同様に、ノード間の移動が発生する。

セグメント木ではこれをビットシフトや再帰で計算していたが、BITではノードの添え字を2進数で表したときの“1”であるビットの位置を利用して計算する。

ノード間の移動では特に、「最下位が“1”であるビットの位置」を順次取得することになる。

これは符号付き2進数を用いて \(a \land -a\) で求めることができる。

\[\begin{split}\begin{eqnarray} 6 \land -6 &=& 0110_{(2)} \land 1010_{(2)} \\ &=& 0010_{(2)} \\ \end{eqnarray}\end{split}\]

\(a \land -a\) の計算結果はビットが1か所だけ立つ。この場所が「最下位が“1”であるビットの位置」となる。

実装

BITは1-indexedで値を保持することに注意。

def bit_init(a):
    """BITの初期化"""
    n = len(a) + 1
    bit = [0] * n
    for i in range(n-1):
        bit_add(bit, i+1, a[i])
    return bit

def bit_sum(bit, i):
    """[0, i)の区間和を求める(1-indexed)"""
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def bit_add(bit, i, x):
    """i番目の値をxだけ増加させる(1-indexed)"""
    while i < len(bit):
        bit[i] += x
        i += i & -i

A = [3, 5, 7, -4, 2, -3, 4]
B = bit_init(A)
print(bit_sum(B, 4))
bit_add(B, 4, 5)
bit_add(B, 5, 6)
print(bit_sum(B, 4))

11
16