まず、セグ木自体は難しいものではないので、変な先入観は無くしましょう。 以下は、再帰の知識がなくても読めるように心がけます。
「何から始めたらいいかわからない」という人は、とりあえず最初に述べるセグ木を理解するところから始めるといいと思います。
導入
次の操作ができる配列だと見なせます。
- 長さ \(n\) で初期化する
- \(i\) 番目の要素の値を \(x\) にする
- \(l\) 番目から \(r\) 番目までの和を求める
初期化は \(\Theta(n)\) 時間で、残りは \(O(\log(n))\) 時間です。実装によっては区間和は \(O(\log(r-l))\) 時間だったりします。
実装
長さ \(2n\) の配列 \(a[2n]\) を用意して、\(a[i]\) (\(1\le i\lt n\)) を \(a[2i]\) と \(a[2i+1]\) の親と見なす木を考えます。
二分ヒープ（std::priority_queue の内部実装で用いられるデータ構造）でも同じ親子関係の木構造を使っているので、それを調べてみても面白いかもしれません。
そして、セグ木では \(a[i]\) は \(a[2i]+a[2i+1]\) の値を持ちます。
初期化や更新の際には、この性質を保つように計算していきます。 また、区間和を求めるときは、なるべく少ない個数の \(a[\ast]\) で所望の和を表します。
やりたいことはこれだけです、単純ですね。実装も短いです。
詳細は セグ木スライド を見るといいです。
抽象化
抽象化と聞くと難しそうと思う人もいるらしいです。 何も難しいことではなくて、「さっきまでは区間の和を求めてたね」「和以外の演算も区間でできたらうれしいな」程度の話です。
実装をよく見ると、所望の演算が結合法則さえ満たせばいいことがわかります。 \( (x+y)+z = x+(y+z)\) のことです。
たとえば、\(a[3] + a[4] + a[5]\) を計算したいとしましょう。 \(a[2] = a[4] + a[5]\) ですから、\(a[3] + a[2]\) を計算することになります。 このとき、次のようになってしまうような演算では困るということです。 \[(a[3]+a[4]) + a[5] \neq a[3] + a[2] = a[3] + (a[4]+a[5]).\]
なお、演算の順序を入れ替える（\(a[4]+a[3]+a[5]\) のようになってしまう）ことはないので、交換法則は要求しません。 また、（足し算に対する引き算のような）逆演算も不要です。
このことを踏まえると、区間における最小値とか、最大公約数とか、いろんなことを求めたくなりますね。 いきなり「区間における最小値を教えて」とか言われても安心です。
群論の用語が出てくるときの話
「モノイドを載せる」とかよく言われますが、要するに「結合法則を満たしていてくれ〜」「単位元があってくれ〜」という気持ちです（用語がわからなければ適宜調べましょう）。
単位元は必ずしもなくていいですが、配列の初期化や、区間和の返り値の初期化の際に便利です。 空区間の区間和が定義できるのもうれしいです（余計な分岐を減らせるので）。
想定される発言
「BIT 書いたから」
BIT、bit 演算をしなきゃで大変じゃないですか？ それを書いたならセグ木なんてすぐできます。
それから、BIT は機能が制限されていて、セグ木ではできて BIT ではできないケースがあります。 「この区間の最小値を求めてね」のようなクエリがくると大変です。 値を任意に変更できる場合だと、先頭からの最小値ですらつらいんじゃないかな。
亜種たちについて
「双対・遅延」←これはできる操作の話です。
「2D・永続・動的」←これもできる操作の話ですが、大きく変わります。
非再帰セグ木
上で紹介したセグ木です。 非再帰-主*1-非遅延-1D-短命*2-静的 セグ木？ 誰もそんな呼び方はしていません。
再帰セグ木
再帰バージョン。非再帰に比べて引数がたくさんいる。定数倍が重いらしい。大変そう。 書きたくなったら書けばいいと思います。
双対セグ木
もっといい名前があればうれしいです。おまけっぽさがかわいそう。
「要素に対する更新・区間の和」をするセグ木の逆で、「区間に対する作用・要素一つの取得」をするデータ構造です。
次に紹介する遅延セグ木を理解してから考える方がいいかもしれません。 可換な作用（区間に対して値を足すなど）であれば、難しい工夫はいらないので、上で述べたセグ木を理解すれば書けるとも思います。
遅延セグ木
「区間に対する作用・区間の和」の両方を処理できるデータ構造です（つよい！）。 定数倍はちょっと重めです。
元のセグ木では、親は子たちの和を持っていましたが、今回は子たちへ行う作用の情報も持つようにします。
たぶん これ を見るといいです。
配列を 2 べきにしてるのとか、配列を 0-indexed で使っているのとか、再帰で実装しているのとかは宗派によるものです。 やりたいことさえわかっていれば、自分の好みに合う方に書き換えられます。
2D セグ木
二次元です。二次元平面上で、「この矩形領域の和は？」とかを処理します。
永続セグ木
永続データ構造です。 最新の状態以外へのクエリも処理できます。「この時点でのこの区間の和は？」といった具合です。 更新クエリを最新の状態に対してしか行えないもの（バージョンを頂点としてグラフを作るとパス状になる）は部分永続と呼ばれます。 一方、古いバージョンについても更新できるもの（バージョンのグラフが木状になる）は完全永続と呼ばれます。
動的セグ木
サイズに対して動的の意味で使われます。
「区間最小値クエリができるけど更新はできないよー」という静的データ構造（sparse table など）に対する「動的」ではないです。
任意位置での insert/erase などが可能です。
平衡二分木でセグ木を作ると言えば（平衡二分木とセグ木を理解している人には）わかりそう？ 要するに、平衡二分木（赤黒木とか AVL 木とか）の葉ノードに配列の各値を入れて、内部ノードに区間和の値を入れるなどをします。 論文などの文脈では、これを指して segment tree [Bentley 1977] と呼ばれることが多そうです？
Starry sky 木
おまけ。
「区間加算・区間最大値」の両方を処理できる + 逆元を要求するデータ構造で、定数倍が軽いとされています。
「区間加算・区間最大値ができる遅延セグ木」の意味で Starry sky 木と呼ぶ人もいますが...。 えびちゃんが「原義 Starry sky 木」と言ったら、ここで紹介されているものを指しています。
典型考察
さっきのスライド の最後の方にもありますが、平面走査を行いながらセグ木で更新していくのは、よくあると思います。
がんばって
「必要になるまでやらない」というのはもったいないです（というか「必要になった」というのは曖昧で、無限に先延ばしが可能なので）。
「BIT でもできるもん」というのもわかりますが、併せて覚えちゃう方が効率がよくないですか？ というか「できるもん」は必ずしも真ではないですし。 「ロリハでできるもん」と言って KMP 法や Z algorithm を勉強しない人さん......*3。
「集合に値を追加する・最小値を取り出す」をしたいな〜と思うことがあるように、「配列の値を更新する・区間和を求める」をしたいな〜と思う場面に出くわすかもしれませんから、早いうちにお勉強して損はないと思います。
おわり
セグ木以外のお勉強を敬遠しているえびちゃんへ
お勉強してください
えびちゃんより
