【セグメントツリー】
セグメントツリー とは？
最終更新:
💡 「この範囲の合計は？」を、区間のメモで素早く調べる木
セグメントツリーは、配列の区間ごとの合計や最小値などを木にまとめるデータ構造です。区間の問い合わせと1要素の更新、計算量の前提、累積和や遅延伝播との違いを図と会話で説明します。
📌 このページのポイント
ひよこ 普通の配列と何が違うの？
ペンギン先生 配列で範囲の合計を毎回一つずつ足すと、その範囲の長さに応じた時間がかかる。セグメントツリーは、区間の合計などをあらかじめ木にまとめるよ。必要な区間のメモを組み合わせて、問い合わせに答えるんだ。
ひよこ 区間のメモは、どうつながるの？
ペンギン先生 葉は配列の各要素、親は子の区間を合わせた情報を持つ。合計なら左右の子の合計を足し、最小値なら小さい方を選ぶよ。まとめる順番を変えても結果が同じになる結合則と、空の区間に対応する単位元が必要だね。
ひよこ 値を一つ変えたら、全部作り直す？
ペンギン先生 その葉と、根までの経路にあるメモを更新する。基本の構成では、問い合わせと1要素の更新はO(log n)、最初の構築はO(n)だよ。ただしメモを組み合わせる計算などを定数時間で行える前提で、何でも一瞬になるという意味ではないんだ。
ひよこ 合計だけなら累積和でもよい？
ペンギン先生 値を変えずに範囲の合計を何度も聞くなら、累積和を作って差を取る方法もあるよ。セグメントツリーは値の更新と問い合わせを繰り返す場合や、最小値など別の集約に使える。必要な操作に合う道具を選ぼう。
ひよこ 範囲をまとめて更新することもできる？
ペンギン先生 遅延伝播を使う構成では、区間へ適用する更新をメモし、必要なときに下へ伝える。ただし区間の集約を更新できること、更新同士を合成できることなどが必要だよ。合計の区間へ同じ値を足す例なら、要素数も使って新しい合計を求める。任意の更新が自動で対応できるわけではないね。
まとめ：ざっくりこれだけ覚えればOK！
「セグメントツリー」って出てきたら「区間ごとのメモを木にして、範囲の値を調べる仕組み」と思えばだいたいOK！
📖 おまけ：英語の意味
「Segment Tree」 ＝ 区間木
💬 Segment（区間・部分）とTree（木）で、区間ごとの情報を木構造にまとめたものだよ