初めましてクマーと申します。軽く自己紹介すると、現在大学1年生で、今年の４月にAtCoderを始めました。現在は主にAtCoder、Codeforcesで競プロをやってます(ユーザ名はどちらもKite_kumaで両方青色です)。
ところで先日遅延セグ木を勉強したのですが、これまでに勉強したどのデータ構造よりも仕組みが複雑で、構造の理解から実装までにめっちゃ時間がかかりました。せっかくなので覚えたことを何かの媒体にまとめておきたいななどと思い、このブログを書いています。
ちなみにタイトルは365億倍くらいに盛ってます。
なお実装・記事作成に当たって以下の記事を参考にしました。
非再帰セグ木サイコー！一番すきなセグ木です
https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf
この記事での実装方針
セグ木にもいろいろな種類・流派がありますが、この記事での実装方針を先に言っておきます。
・非再帰
蟻本など再帰セグ木について書かれている文献が多いですがあえて非再帰の方に挑戦しました。理由は再帰しないことにより定数倍が若干軽くなることと、参照するセルの番号の遷移が分かってそうでかっこいい感じがすることです。
・非２べき
要素数Nの配列に対して、セグ木内部ではN以上の最小の２べきをとってそれを要素数にする(あまりの部分には演算の単位元を埋める)という実装方針をよく見ますが、あえて２べきにする必要もないらしいということを知ったのでそちらを勉強しました。遅延とか言いだすと定数倍が重くなるので、余計に演算回数を増やすのはやめるに越したことはないのかななどと。
・1-indexed
基本的に0-indexedの方が好きなんですが、セグ木に関しては1-indexedの方が見やすいと思います。理由はセルの親子関係が分かりやすいこと、元の配列データを入れる部分がN-indexed(?)になることです。
・非遅延/遅延 (点更新/区間更新)
両方作りました。区間更新できる後者は一応前者の上位互換ではあるのですが、さすがに定数倍が違い過ぎるので両方持っていて良いと思います。
・抽象化
関数をラムダ式で渡すことで問題ごとに都合よく演算処理を変更できます。遅延セグ木の方は問題ごとに渡す関数を考えるだけでも意外に大変だったりしたのでその話もまた書こうと思います。
セグ木ってなんやねん
まずセグ木について軽く書きます。セグ木とは長さNの配列中の連続した区間の合計値/最小値/最大値/最大公約数/xor/行列積などをO(logN)で計算するデータ構造です。
下図は点更新・区間合計値取得型のセグ木の図です。
(N = 8 の画像)
ポイントは
- 番号が1~N*2-1のN*2-1個のセルを使った木構造をもつ
- 元の配列データは[N,N*2)の区間(図の最下段)に置く
- 1-indexedで書く(0-indexedより分かりやすい)
- 常に(親ノードの中身) = (2つの子ノードの中身の和)を保つ
- 値が更新されるたびに、その真上の部分を更新
- セル番号 i の子のセル番号は i*2 と i*2+1
といったところです。２べきの形でデータを持つことによって区間クエリに対して強い形となっています。例えば区間[9,14)の合計値(元データにおける[1,6)の合計値)を取得したいときは9,5,6番のセルを見て足し合わせればいいですね(上図赤色)。
上の図はNの値が小さく、普通に5つのデータを全部足し合わせても大差ないのですが、その手法だとNが大きくなるとO(N)かかってしまいます。この形でデータを保持すればどのような区間に対してもO(logN)個のセルを足し合わせるだけで答えを求めることができます。ちなみにlogNというのはこの木構造の高さに相当しています。
更新の際には図のように下から上にかけて１つずつセルを更新していきます。こちらも同じくO(logN)でできます。セル番号の遷移は右シフト(2で割り算して切り下げ)ですね。
結果として、愚直に区間中の要素を１つ１つ足していく実装と比べると「あらかじめ急所の区間和をO(logN)かけて計算しておくことによってクエリにO(logN)で対応できるようにしている」わけです。
さて動く原理はこれで分かったわけですが、実際に区間の合計値を求める際に参照するセルをどのように選んでいけばよいのでしょうか。
例えば半開区間 [l, r) について合計値を求めることを考えてみます。実装の方針は意外にシンプルで、
- lが奇数ならばセルlの値を足す。lをインクリメントする。
- rが奇数ならばセルr-1の値を足す。rをデクリメントする。
- l,rを右に1シフトさせてl',r'とする。１つ上の段の区間の合計値[l',r')を求める
これをl == rになるまで繰り返すだけです。
ちなみにこの実装は要素数Nが２べきでなくとも通用します。下の図ではN=11です。
先程と同じく、元データを最下段において、「セル番号 i の子のセル番号は i*2 と i*2+1」と言うルールでセルを置いてあります。
図の灰色のセルには特に意味のない値が入ったりしますがクエリ処理の際に呼び出されることはないので大丈夫です。実際、例えば区間[13,21)を求める際、[l,r)の遷移は
[13,21) -> [7,10) -> [4,5) -> [2,2)
となり、13,20,7,4番のセルの値を参照することになりますが、灰色のセルに届く前に l == r となって遷移が終了します。面白いですね。
というわけで非遅延・非再帰・非２べきセグ木についてはこれで終わりです。抽象化については詳しい記事が他にもあるのでそちらを参照してください。(再掲・再帰で書いてあります)
注意すべきことですが、抽象化の際には演算を指定する関数だけでなく演算の単位元を用意する必要があります。例えば加算の単位元は0,乗算の単位元は1,最小値の単位元はINF,最大値の単位元は-INFです。
また行列積など交換法則が適用されない演算もあるので、演算の左右については慎重に実装しましょう。区間の左側の演算結果と区間の右側の演算結果を持っておいて(初期化は単位元で行う)、最後にそれをマージする方針でできます。
長くなって疲れたので遅延セグ木の話は次回にします。
