🌳 BIT木構造の詳細解析
1. BIT（Binary Indexed Tree）の基本構造
BITとは？
Binary Indexed
Tree（フェンウィック木）は、配列の要素に対する一点更新と区間和クエリを効率的に処理するデータ構造です。
各ノードは特定の範囲の和を保持し、木構造により高速な操作が可能になります。
1.1 配列からBIT木への変換過程（n=8の場合）
💡 各ノードをクリックすると、そのノードから根までのパスがハイライトされます
1.2 親子関係の数学的解析
🔢 ビット演算の核心
親 = i + (i & -i)
i & -i は「iの最下位の1ビット」を取得する演算です
例: 6 & -6 = 010₂ = 2
6 = 110₂, -6 = 010₂, 6&-6 = 010₂ = 2
🎯 2の補数による計算
数値 5 の場合: 5 = 101₂ (binary) -5 = 011₂ (2の補数) 5 & -5 = 001₂ = 1 親 =
5 + 1 = 6
2. 最短パス探索アルゴリズムの詳細
2.1 インタラクティブパス計算
2.2 典型的なパス探索例
例1: 頂点1からのパス (n=8)
計算過程:
1: 1 & -1 = 1, 親 = 1 + 1 = 2
2: 2 & -2 = 2, 親 = 2 + 2 = 4
4: 4 & -4 = 4, 親 = 4 + 4 = 8
8: 8 > n=8, 根(0)到達
例2: 頂点5からのパス (n=8)
計算過程:
5: 5 & -5 = 1, 親 = 5 + 1 = 6
6: 6 & -6 = 2, 親 = 6 + 2 = 8
8: 8 > n=8, 根(0)到達
3. アルゴリズムの計算量解析
⏱️ 時間計算量
O(log n) per query
各頂点から根までの距離は最大でlog₂(n)です。これは数値の2進表現のビット数に対応しています。
💾 空間計算量
O(log n)
パスの長さが最大log₂(n) + 1なので、格納に必要な空間も同程度です。
4. 実装コードの詳細解説
def find_path_to_root(n: int, start_vertex: int) -> List[int]: path: List[int] = []
# パスを格納するリスト current: int = start_vertex # 現在の頂点 while current != 0:
# 根に到達するまでループ path.append(current) # 現在の頂点をパスに追加 #
親の計算：最下位ビットを加算 parent: int = current + (current & -current) if parent
> n: # 親がn超過なら根到達 current = 0 else: current = parent path.append(0) #
根(0)を追加 return path
5. BIT木構造の利点
なぜBITが効率的なのか？
1. バランス性: 完全に平衡な木構造により安定した性能
2. 局所性: 更新時に影響する頂点が対数個に限定
3. ビット演算: 高速な親子関係の計算が可能
4. メモリ効率: 配列ベースの実装でキャッシュ効率が良い
🎉 まとめ
BITの木構造における最短パス探索は、ビット演算を巧妙に活用することで対数時間での効率的な実行を実現しています。
この理解により、より高度なデータ構造やアルゴリズムへの応用も可能になります。