BIT (Binary Indexed Tree) 詳細解説

📊 BITとは？

Binary Indexed Tree (BIT)は、配列の区間和クエリと要素の更新を効率的に処理するデータ構造です。

通常の配列では区間和の計算にO(n)時間がかかりますが、BITを使用することでO(log n)で実行できます。

操作	通常の配列	BIT
要素の更新	O(1)	O(log n)
区間和クエリ	O(n)	O(log n)
空間計算量	O(n)	O(n)

🎯 インタラクティブデモ

元の配列

BIT構造

インデックス:

値:

開始:

終了:

🔢 BITの仕組み

BITの核心は最下位ビット（LSB）の概念です。各インデックスが管理する範囲は、そのインデックスの二進表現の最下位の1ビットによって決まります。

LSB の計算方法:

LSB(x) = x & (-x)

例：
6 (110₂) の LSB = 110₂ & 010₂ = 010₂ = 2
8 (1000₂) の LSB = 1000₂ & 1000₂ = 1000₂ = 8

各インデックスが管理する範囲:

💻 実装コード

class BIT {
    constructor(n) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
    
    // LSB（最下位ビット）を取得
    lowbit(x) {
        return x & (-x);
    }
    
    // インデックス i に値 delta を加算
    update(i, delta) {
        while (i <= this.n) {
            this.tree[i] += delta;
            i += this.lowbit(i);
        }
    }
    
    // インデックス 1 から i までの累積和を取得
    query(i) {
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= this.lowbit(i);
        }
        return sum;
    }
    
    // インデックス l から r までの区間和を取得
    rangeQuery(l, r) {
        return this.query(r) - this.query(l - 1);
    }
}

🎓 応用例

BITが活用される場面：

競技プログラミング: 区間和クエリが頻繁に発生する問題
統計処理: リアルタイムでの累積統計計算
ゲーム開発: スコアランキングシステム
データ分析: 時系列データの区間集計

類似データ構造との比較：

セグメント木: より汎用的だが、実装が複雑
平方分割: 実装が簡単だが、計算量が劣る
累積和配列: 更新がO(n)と非効率

🌳 BIT (Binary Indexed Tree) 完全解説