セグメントツリー とは？

普通の配列で「3番目から7番目までの合計は？」と聞かれたら、1個ずつ足していくからO(n)かかる。セグメントツリーなら事前にツリーで区間の情報をまとめておくから、O(log n)で答えられるんだよ

配列の各要素を葉ノードにして、親ノードに「子2つの合計」や「子2つの最小値」を持たせるんだ。根に近いほど広い区間をカバーしていて、必要な区間だけをたどれば答えが出るよ

いや、変わった要素から根までのパスだけ更新すればいい。木の高さはlog nだから、更新もO(log n)で済むんだ。これが配列を毎回再計算するより圧倒的に速いポイントだよ

「3番目から100番目まで全部+5して」みたいな区間一括更新のとき、全ノードを即座に更新せず「あとで反映するメモ」を残しておくテクニックだよ。必要なときだけメモを解消するから、区間更新もO(log n)で処理できるんだ

競技プログラミングでは超頻出だし、実務ではデータベースの範囲検索インデックスや、ゲームのダメージ計算、地理情報の区間クエリなどに応用されるよ。知っておくとアルゴリズムの引き出しが一気に広がるデータ構造だね