Binary Indexed Tree (BIT, Fenwick Tree)

概要

整数列 に対して, 以下のクエリを O(log(n)) で実現するデータ構造.

1. : を求める
2. : に を加える

特徴

Segment Tree の機能縮小版で, 実装がむちゃくちゃ簡単.

構造

深さ log(n) の二分木であり, 各ノードは以下の法則で値を保持する.

1. 葉:
2. 葉の親:
3. 葉の親の親: [tex: a_1+a_2+a_3+a_4,\ a_9+a{10}+a{11}+a_{12}, \dots]

クエリ処理は, 葉から根へ高々 log(n) 回の計算で完了する.
例えば, は で求められる.

用途

転倒数 (inversion) を求めるなど

実装に関する補足

木を配列としてうまく持つことで実装がものすごく簡易になる. 詳細は下記ページを参照.

TopCoder Algorithm Tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
わかりやすいスライド: http://hos.ac/slides/20140319_bit.pdf

実装

class BIT
{
public:
    vector<int> bit;
    int M;

    BIT(int M):
        bit(vector<int>(M+1, 0)), M(M) {}

    int sum(int i) {
        if (!i) return 0;
        return bit[i] + sum(i-(i&-i));
    }

    void add(int i, int x) {
        if (i > M) return;
        bit[i] += x;
        add(i+(i&-i), x);
    }
};

暗唱のポイント

• 1-indexed
• (i&-i) で rightmost set bit だけ取り出せる
• 木 について, sum は重ならない方向(左), add は重なる方向(右)