Binary Indexed Tree (Fenwick Tree)

コードについての説明

BIT(binary indexed tree) は1点加算と区間和のクエリを高速に処理することのできるデータ構造. Fenwick Tree とも呼ばれる. Segment Tree を用いても実装できるが BIT の方が基本的に速い.
理由としてはメモリを 2 冪にそろえる必要がないこと(もちろん完全平衡二分木でないようなものに対しても Segment Tree を考えることはできるけど実装的にサイズは 2 冪で取ることが多い), 計算が非再帰かつビット演算を用いて遷移が可能であること, 例えば $i$ 番目の要素に加算する場合にかかる計算量が数 $i$ の立っているビットの数に比例することなどがある(Segment Tree では必ず $\Omega(\log n)$ 回かかる).
説明はおそらく検索すればわかりやすいものがいくつも出てくると思うので他のかたにゆずることにする...
ブロックの持ち方をフィボナッチ数にすることで $\log$ の底が変わり計算量的には速くなるという話もある(参考). (実測はたぶん速くならない)

時間計算量: 構築 $\O (n)$, 各クエリ $\O (\log n)$

コード

class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        index += 1
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        index += 1
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

verify 用の問題

AOJ : Range Sum Query (RSQ) 提出コード