🌳 BIT (Binary Indexed Tree) 詳細解析

1. BITの基本概念

Binary Indexed Tree (BIT) / Fenwick Treeは、配列の区間和クエリと一点更新を効率的に行うデータ構造です。

🎯 主な特徴

2. 配列からBITへの変換

📊 元の配列 A = [1, 5, 7, 9, 8, 6]

1
A[1]
5
A[2]
7
A[3]
9
A[4]
8
A[5]
6
A[6]

🔄 BIT構築プロセス

各BIT[i]は、特定の範囲の要素の合計を格納します。

BIT Index バイナリ 担当範囲 計算 値
BIT[1] 001 A[1] 1 1
BIT[2] 010 A[1] + A[2] 1 + 5 6
BIT[3] 011 A[3] 7 7
BIT[4] 100 A[1] + A[2] + A[3] + A[4] 1 + 5 + 7 + 9 22
BIT[5] 101 A[5] 8 8
BIT[6] 110 A[5] + A[6] 8 + 6 14

🌲 BIT構造の可視化

22
BIT[4]
6
BIT[2]
14
BIT[6]
1
BIT[1]
7
BIT[3]
8
BIT[5]

3. LSB (最下位ビット) の重要性

🔧 LSB計算式: idx & (-idx)

例：idx = 6 の場合
6 (binary): 110
-6 (binary): ...11111010 (2の補数)
6 & (-6) = 110 & ...11111010 = 010 = 2

LSBは、そのインデックスが担当する範囲の大きさを示します。

4. 一点更新の詳細プロセス

📝 例：A[5]に10を加算する場合

🛤️ 更新パス計算

インデックス5から開始して、LSBを加算しながら進む：

5
→
6
→
8
計算過程：
5 (101) → 5 + (5 & -5) = 5 + 1 = 6
6 (110) → 6 + (6 & -6) = 6 + 2 = 8
8 > 6 なので終了

📊 更新前後の比較

BITインデックス 更新前 更新後 変化
BIT[5] 8 18 +10
BIT[6] 14 24 +10
その他 変更なし 変更なし 0

5. アルゴリズムの実装解析

🏗️ BIT構築アルゴリズム

function buildBIT(A) { const n = A.length; const BIT = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) { let idx=i; while (idx <=n) { BIT[idx] +=A[i - 1]; idx +=idx & (-idx); // LSB加算 } } return BIT; }

🔄 一点更新アルゴリズム

function updateBIT(BIT, pos, val) { let idx = pos; while (idx <= BIT.length - 1) { BIT[idx] +=val; idx +=idx & (-idx); // 次の更新位置 } }

6. 計算量分析

⏱️ 時間計算量

💾 空間計算量

7. 具体例でのシミュレーション

🎮 入力例：A = [1, 5, 7, 9, 8, 6]

初期BIT: [0, 1, 6, 7, 22, 8, 14]

クエリ1: A[5] += 4

更新パス: 5 → 6

結果: [0, 1, 6, 7, 22, 12, 18]

クエリ2: A[1] += 10

更新パス: 1 → 2 → 4

結果: [0, 11, 16, 7, 32, 12, 18]

8. まとめ

🎯 BITの核心

  1. LSB操作により効率的な木構造を実現
  2. バイナリ表現が更新パスを決定
  3. 部分和の重複管理により高速化
  4. メモリ効率が良く実装が簡潔