セグメント木（Segment Tree）
完全二分木による範囲クエリと一点更新の効率的な処理。分割統治法の美しい実現
O(log n)
クエリ・更新
O(n)
構築時間
中級
難易度
O(4n)
空間計算量
🌳 セグメント木操作設定
操作:
セグメント木の構築
クエリタイプ:
合計
🎯 分割統治による効率的な範囲処理
📚 推奨操作例
🌳
セグメント木操作を実行してください
左側の入力パネルから操作を設定し、「セグメント木操作実行」ボタンを押してください
🎯 セグメント木の特徴と応用
構造的特徴
- • 完全二分木による分割統治
- • 配列による効率的実装
- • O(log n)の範囲アクセス
- • 多様な結合演算対応
実用的応用
- • 範囲クエリの高速処理
- • データベースのインデックス
- • 動的プログラミング
- • 競技プログラミング
💡 学習ポイント: セグメント木は分割統治法の美しい実現であり、 様々な結合可能演算に対して汎用的な範囲処理を提供します。