🌳 BIT構築の詳細解析

📊 1. 入力配列とBIT配列の関係

例: A = [1, 5, 7, 9, 8, 6]

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

🔢 2. 各BIT[i]の計算過程

1
BIT[1]の計算

i = 1 → 2進数: 0001

1を2で割ることができる最大回数 k = 0

2^k = 2^0 = 1

BIT[1] = A[1-1+1-1] = A[0] = 1
2
BIT[2]の計算

i = 2 → 2進数: 0010

2を2で割ることができる最大回数 k = 1

2^k = 2^1 = 2

BIT[2] = A[0] + A[1] = 1 + 5 = 6
3
BIT[3]の計算

i = 3 → 2進数: 0011

3を2で割ることができる最大回数 k = 0

2^k = 2^0 = 1

BIT[3] = A[2] = 7
4
BIT[4]の計算

i = 4 → 2進数: 0100

4を2で割ることができる最大回数 k = 2

2^k = 2^2 = 4

BIT[4] = A[0] + A[1] + A[2] + A[3] = 1 + 5 + 7 + 9 = 22

⚡ 3. ビット演算による最適化

i & -i による最下位ビット取得

i = 6 (0110) -i = -6 (1010) // 2の補数 i & -i = 0010 = 2 i = 8 (1000) -i = -8 (1000) i & -i = 1000 = 8

この演算により、2^kの値を直接取得できます！

📈 4. 計算量解析

時間計算量: O(n log n)

k値 該当するi の個数 各iの計算コスト 総コスト
0 n/2 1 n/2
1 n/4 2 n/2
2 n/8 4 n/2
... ... ... ...
合計 - - O(n log n)

🌲 5. BITの木構造

0
4
6
2
3
5
1
1
1
1
1
1

各ノードは対応するBITのインデックスを表します

🚀 6. インタラクティブデモ

配列の値を変更してBITの変化を確認できます：

💡 7. 実装のポイント