Fenwick Tree（Binary Indexed Tree）
ビット演算による累積和の巧妙な実装。lowbit操作で効率的な範囲管理を実現
O(log n)
更新・クエリ
O(n log n)
構築時間
中級
難易度
O(n)
空間計算量
🔢 Fenwick Tree操作設定
操作:
Fenwick Tree構築
🎯 ビット演算による累積和管理
📚 推奨操作例
🔢
Fenwick Tree操作を実行してください
左側の入力パネルから操作を設定し、「Fenwick Tree操作実行」ボタンを押してください
🎯 Fenwick Treeの特徴と応用
技術的特徴
- • lowbit操作（x & -x）の活用
- • 1-based配列による実装
- • シンプルで高速な実装
- • セグメント木より省メモリ
実用的応用
- • 累積和の動的計算
- • 転倒数（逆順ペア）計算
- • 競技プログラミング
- • リアルタイム統計処理
💡 学習ポイント: Fenwick Treeはビット演算の巧妙な活用により、 累積和に特化した最適化を実現した実用的なデータ構造です。