まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
おこていゆ = NokonoKotlin
セグメントツリーって良い響きですよね。気になる異性の前でドヤ顔で口にしたいワード No.1 です。
この記事ではセグメント木の雰囲気だけ紹介して、実装などのテクニックなどは詳しくは紹介しません。
用語
はじめに、セグメント木に関する (自分がよく使う) 用語を定義しておきます。
- セグメント := セグメント木のノード、またはノードがカバーする範囲(区間)
- 集約 := ノードが持つ値をマージ (合併) する。
- 評価 := ノードに持たせている評価値から、ノードの値や集約値を評価 (計算) すること (作用とも言う)
- 伝播 := 遅延している 評価 を子ノードに降ろすこと (伝搬ではありません)
セグメント木とは？
単にセグメント木と言った場合、普通は以下のような完全二分木の構造を指します。セグメント木は、完全二分木の末端 (葉) の要素と列の要素を対応させることで、列に対する操作を効率的に行います。左から $i$ 番目の葉は列の $i$ 番目の要素に対応しており、便宜上区間 $[i,i+1)$ に対応するセグメントとして定義します。
以下は長さ $8$ の列 $4,3,4,0,-2,3,1,2$ に対応するセグメント木です。
セグメント木のノード (セグメント) は、以下のルールに従って構築されます。
- 左右の $2$ つの子セグメントがカバーする区間を過不足なくカバーする。
- 左右の子ノードが持つ集約値をそれぞれマージして、自身の集約値として持つ。
このように構築したセグメント木では、あるセグメントが持つ集約値は、そのセグメントがカバーする区間の列の要素の総和になっています。このことを利用して列の区間の総和を計算するクエリを処理することができます。
総和を取得したい区間に対して、その区間を過不足なくカバーするようにいくつかのセグメントを選びます。このとき、選ぶセグメントを適切に決めることで、セグメントの個数を $O(\log{(区間幅)})$ 個に抑えることができます。
今回の集約は要素の和なので、選択したセグメントの集約値をさらに集約することで、区間内の列の要素の総和を計算することができました。適切に実装することで、計算時間はクエリあたり $O(\log{(区間幅)})$ 時間になります。
基本的に一番上のノードから下に降りてセグメントを選択する方針が見通しが良いです。理由は後にわかりますが、基本的にノードへのアクセスは根から探索を行なってアクセスするものとします。
列の要素を変更したときの処理
列の要素を変更すると、その上側のノードの集約値も変更する必要があります。
列の要素を変更した後、祖先のセグメントに登り、下から木 DP のように左右の子の集約をマージし直していくことで、更新があった要素の影響を上側のセグメントにも反映させることができます。
この処理の計算量は図の矢印の本数で抑えることができ、$O(木の高さ) = O(\log{(列のサイズ)})$ 時間で実行できます。
ちょっと一般化
今紹介したセグメント木は 一点更新 / 区間取得 タイプのセグメント木です。例に挙げたセグメント木では区間取得の種類が区間の総和でしたが、集約の演算を別のものに設定することで別の区間取得をサポートするセグメント木にすることができます。例えば、集約の種類を min にすると、区間 min をサポートします。
セグメント木における区間内要素の集約は、分解すると $2$ のデータの集約を結合したものとなるので、集約は結合できる二項演算で一般化することができます。セグメント木に乗せることができる二項演算はモノイドという演算に分類されます。
双対セグメント木
wikipedia によると 「双対」とは「互いに対になっている2つの対象の間の関係である」ことを指すとあります。双対セグメント木がどう双対なのかはぼくどんの知るところではありませんが、先述の処理と似たような操作をすることで 一点取得/区間更新 という別のタイプのセグメントツリーを構築することができます。
双対セグメント木のノードには、集約の代わりに評価値を持たせます。ある値に評価値を反映させる計算を評価と呼び、評価にはモノイドが乗ります。
はじめ、全てのノードには評価の単位元 (ある値に評価しても値が変化しないもの) を持たせておきます。
双対セグメント木で区間更新を行う際も、通常のセグメント木の区間取得と同様に区間に対応するセグメントを選択します。列の区間内の要素を全て更新する代わりに、選択したセグメントに区間を代表して更新をかけます。
今回の例は 一点取得/区間加算 タイプです。選択したセグメントにのみ評価を加算し、他のセグメントは見ないことで区間加算の計算量を $O(\log{(区間幅)})$ 時間で抑えています。
また、評価はモノイドなので複数の区間加算の結果を結合して保持することができます。
列の一点を取得は、その一点をカバーするセグメントが持つ評価値を全て評価 (結合) したものを計算することで処理できます。
上記の例では $7$ に $0,4,0$ を順に評価します。今回の評価は加算なので、結果は $(((7+0)+4)+0) = 11$ です。
遅延評価セグメント木
先の $2$ 種類のセグメント木は、値の集約 と 値の評価 のどちらか片方のみを持つセグメント木でした。それに対して遅延評価セグメント木は、値の集約 と 値の評価 の両方を持つセグメント木です。遅延評価セグメント木は 区間取得/区間更新 タイプのセグメント木で、多くの場合は先に紹介した $2$ 種類の上位互換として機能します。
今回は 区間和/区間加算 をサポートする場合を例に挙げて考えます。基本的な構造は通常のセグメント木と同じですが、評価の扱いを少し変えて遅延評価として保持します。
以下のように、区間 $[0,6)$ に一律に $-5$ 加算する場合の処理を見てみましょう。
双対セグメント木のように、評価を保持する代表セグメントを選択することで解決を計ります。
この際、選択したセグメントの評価値を更新することに加えて、セグメントが持つ集約値も評価する必要があります。この場合、集約値は左右の子ノードの集約値から再計算することはできず、評価するセグメント自信が持つデータ と 評価値 から正しい集約値を再計算することができる必要があります。
今回の場合は集約が区間和 , 更新が区間加算なので、元の集約値に $セグメントの幅 \times 評価値$ を加算することで、セグメント自身が持つ値のみから正しい集約値を再計算することができました。
しかし、遅延評価セグメント木の区間加算には双対セグメント木の場合とは決定的に異なることがあります。今、加算する区間を代表するセグメントに評価を反映することには成功しました。しかし今回のセグメント木では、評価する区間と重複部分があるセグメント全てに対して評価を反映する必要があります。
上記のピンクで塗られたセグメントの集約値には、区間加算の結果が反映されていません。このピンクのセグメントのうち、上側と下側で別の処理を行うことで、セグメント木全体に評価を行き渡らせます。
上側部分の評価
選択したセグメントを末端として、木 DP の要領で部分木の集約を再計算して行きます。評価する区間を代表して選択したセグメント (赤枠のセグメント) の評価は終わっているので、上側のセグメントに関しては左右の子を見ることで集約を正しく再計算できます。
下側部分の評価
区間を代表して選択したセグメント (赤枠のセグメント) にかかっていた評価を、そのまま左右の子ノードにかけます。これを評価の伝播と言います。
この処理を行なっても依然として下側のセグメントは未評価のままですが、この部分の評価は、この部分のセグメントが必要になるまで遅延させておいても良いです。要するに評価が行われていないセグメントは、次にそのセグメントにアクセスされるまで評価の処理を先延ばしにしておきます。先延ばしにされた評価を遅延評価と言います。
要素へのアクセス
セグメントへのアクセスは根から探索して行うので、その道中で未評価の評価を実行 & 子ノードに伝播を行うことで、アクセスの道中のついでに先ほどの区間の下側セグメントに評価が行き渡ります。
なお評価は結合できるので、評価を溜め込んでおいても何も問題ありません。
今回の評価は加算なので、新たに評価が加わった際は元々存在した遅延評価に加算してから評価すれば良いです。もちろん 上側/下側 のセグメントの評価も行います。
遅延評価が正しく行き渡っているなら、区間取得は通常のセグメント木と同様に行うことができます。ただし、区間取得で選択するセグメントを探索する際も、遅延評価を評価/伝播することを忘れてはいけません。
評価と集約はそれぞれモノイドであれば OK ですが、同時に計算可能かどうかはまた別の問題なので注意が必要です。
動的セグメント木
最後に、セグメント木の空間計算量を減らしたものを紹介します。これの呼び方は「必要なところだけ作るセグ木」派と「動的セグ木」派の $2$ つがあり、「動的セグ木」は平衡二分木を指す場合もあるらしいのですが、ぼくどんは動的セグ木はセグメント木の派生として使っています。
「必要なところだけ作るセグ木」の名の通り、初期状態では対応する列の定義域と列の初期値を持つ根セグメントのみ存在し、クエリで別途セグメントが必要になれば、その都度セグメントを生成します。
集約の計算は、自分自身が持つデータのみから計算します。
以下は定義域が $[0,9)$ で、初期値が $3$ の列に対応する動的セグメント木です。
今回も 区間和/区間加算 のセグメント木を列に挙げて考えます。このセグメント木の各ノードは、集約値 Sum と 値 V を持ちます。ただし、値 V は現在生成されているセグメントのうち末端のセグメントのみ保持し、内部ノードが持つ V は意味を持たないものとします。
この木で区間 $[2,4)$ の区間和を取得してみましょう。区間 $[2,4)$ をカバーするセグメントを選択するために、新たに根の子を生成します。子セグメントを生成するとき、左右の子セグメントがカバーする区間には、自身の区間を中心で $2$ 分割したものを割り当てます。
この時、根が持つ V を新たに生成した左右の子セグメントに継承させます。そして、根が内部ノードになったので今後は根の V を考える必要はありません。
子セグメントを生成するときは、自身の持つ値 (カバーする区間など) から集約値を計算する必要があります。
その後さらに深く降りて、必要なセグメントの生成を続けます。
欲しい区間のセグメントが生成されたら、下に降りるのをやめ、セグメントの集約値を取得してクエリに答えます。
区間加算
区間加算も同様の手順で行います。
選択するセグメントが揃うまで必要なセグメントを生成し続け、選択したセグメントに評価を行います。
セグメントを選択したら、遅延評価セグメント木と同様に、まずは選択したセグメントに対して評価を行います。
その後、上側領域は木 DP の要領で集約を再計算します。ここも遅延評価セグメント木と同様です。
最後に下側に評価を伝播するステップですが、ここはただの遅延評価セグメント木とは少し異なる処理を行います。
セグメントが末端の時、新たにセグメントを生成して遅延評価を降ろすよりも、次に子が生成されるタイミングで評価ずみの V を継承させる方が効率が良いので、セグメントが末端ならば評価を下に伝播させずに解消して OK です。
末端のセグメント以外からは、通常の遅延評価セグメント木と同様に左右の子に評価を伝播させます。
おわり
動的セグメント木は完全二分木である必要はありませんし、根の区間の初期値として定義域を自由に設定でき、アクセスする領域の制限が緩いのが強みです。
初期状態の空間計算量が $O(1)$、区間クエリ 1 回あたりの計算量が、時間/空間 ともに $O(\log{(区間幅)})$ なので、定義域を大きくしても計算量への影響が小さく、またメモリ上の領域として明示的に保持する必要もないので、負の定義域などを設定することもできます。ただし、アクセスするのは整数 index に限定した方が無難です。