通常/双対/遅延評価/動的/二分探索/多次元/全永続セグメント木 (セグ木,セグメントツリー) (コード例付き)

Last updated at 2025-02-26Posted at 2025-02-24

まえがき

この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)

おこていゆ

セグメントツリー(セグ木)って良い響きですよね。気になる異性の前でドヤ顔で口にしたいワード No.1 です。

セグメント木
1. 区間取得
2. 一点更新
3. ちょっと一般化
  1. 集約の例
双対セグメント木
1. 区間更新
2. 一点取得
遅延評価セグメント木
1. 区間更新
  1. 上側部分の評価
  2. 下側部分の評価
2. 遅延評価の伝播
3. 遅延評価のマージ
4. 遅延評価の例 (アフィン変換)
  1. 集約への影響
動的セグメント木
1. 表現
2. 頂点の動的確保
3. 要素アクセス (メモリの節約)
  1. 空間計算量と注意
  2. V について
セグメント木上の二分探索
1. アルゴリズム
2. 活用例 : 順序付き多重集合
  1. 基本機能
  2. ランダムアクセス
  3. 最頻値
  4. 個数が最も少ない要素
  5. 総和の計算
  6. セグ木の遅延評価を用いた機能
  7. 注意点
多次元セグメント木
1. 値の集約
2. 矩形領域取得
  1. 矩形取得の具体的な流れ
  2. 計算量
3. 値の更新
4. 実装
セグメント木の永続化
1. 動的セグメント木の全永続化
2. 根によるバージョン管理
3. 参照の複製によるコピー省略
4. メモリに配慮した戦略
5. 区間アクセス
6. 遅延評価
7. 区間コピー
8. メモリ効率化
まとめ

1 セグメント木

はじめにセグメント木に関する (自分がよく使う) 用語を定義しておきます。

セグメント := セグメント木のノード、またはノードがカバーする範囲(区間)
集約 := ノードが持つ値をマージ (合併) すること
評価 := ノードに持たせている評価値から、ノードの値や集約値を評価 (計算) すること (作用とも言う)
伝播 := 遅延している評価が子ノードに降りること (伝搬ではありません)

セグメント木は二分木によって表現される、以下の図のようなデータ構造です。

セグメント木の各セグメントは半開区間と対応づけられて定義されます。例えば左から $i$ 番目の末端セグメント (葉ノード) は半開区間 $[i,i+1)$ に対応しています。また、末端でないセグメントは自身の左右の子に対応する区間を過不足なくカバーしています。例えば、左右の子がそれぞれ区間 $[0,4)$ と $[4,8)$ に対応するなら、自身は区間 $[0,8)$ に対応します。

例示したセグメント木は、末端セグメントの要素を数列と対応づけることで数列 $\{4,3,4,0,-2,3,1,2\}$ を表現しています。さらに、末端でないセグメントは、自身がカバーする範囲の集約を持ちます。上図のセグメント木の各セグメントは、数列 $\{4,3,4,0,-2,3,1,2\}$ のうち自身がカバーする範囲内の値の総和を持ちます。各セグメントが持つ集約は、自身の左右の子が持つ集約から計算することで再帰的に計算することができます。

なお、セグメント木の末端セグメントは $2$ の冪乗個存在するので、数列のサイズも $2$ の冪乗である必要があります。数列のサイズが $2$ の冪乗でない場合は、集約に影響しない値 (集約が総和なら $0$ , 最小値なら $\infty$ , 最大値なら $-\infty$) で数列を埋めて $2$ の冪乗のサイズまで拡大して対処できます。

1.1 区間取得

セグメント木で表現された列に対しては、列の任意の区間内の要素に対して集約を取得することができます。この処理を、先ほどのセグメント木を用いて要素の総和の場合で説明します。

まず、セグメント木のセグメントを適切に選択することで、総和を計算したい区間を過不足なくカバーできます。以下は区間 $[1,7)$ をカバーするセグメントをうまく選択した様子です。

このように選択したセグメントに対して、それらのセグメントが持つ集約をさらに集約することで、任意の区間に対して集約を計算することができます。今回の例では、数列の区間内の要素 $\{3,4,0,-2,3,1\}$ の総和を、$3+4+1+1 = 9$ のようにして計算できます。

木の根(一番上のセグメント)から探索してセグメントうまく選択することで、区間のカバーに用いるセグメントの個数を $O(\log{(数列のサイズ)})$ 個にできます。適切に実装すると、区間の集約の取得の計算時間は $O(\log{(数列のサイズ)})$ 時間です。

1.2 一点更新

セグメント木で表現された列の要素を変更した時、その変更がセグメント木にどう影響するかを考えてみます。以下は数列 $\{4,3,4,0,-2,3,1,2\}$ の $3$ 番目 (0-index) の要素を $20$ に変更した様子です。

数列の要素を表す末端を変更するのはもちろんとして、その末端をカバーしている他のセグメントの集約を更新する必要もあります。よって、更新した末端セグメントから上にのぼり、道中のセグメントが持つ集約を左右の子の集約から再計算する必要があります。この処理は木の高さ分の再計算を必要とするので、計算時間は $O(\log{(数列のサイズ)})$ 時間です。

1.3 ちょっと一般化

今紹介したセグメント木は一点更新 / 区間取得タイプのセグメント木です。例に挙げたセグメント木では区間取得の種類が区間の総和でしたが、集約の演算を別のものに設定することで別の区間取得をサポートするセグメント木にすることができます。例えば、集約の種類を min にすると、区間 min をサポートします。

セグメント木における区間内要素の集約は、分解すると $2$ つのデータの集約を結合したものとなるので、集約は結合できる二項演算で一般化することができます。セグメント木に乗せることができる二項演算はモノイドという演算に分類されます。

1.3.1 集約の例

ノードが持つ集約として、代表的なものとしては以下があります。

自身以下の部分木内のノードが持つ値の総和 ($\mathrm{Sum}$) $\rightarrow$ 左右の子の $\mathrm{Sum}$ の和
自身以下の部分木内のノードが持つ値の最小値 ($\mathrm{Min}$) $\rightarrow$ 左右の子の $\mathrm{Min}$ と「自身が持つ値」の最小値から計算可能
自身以下の部分木内のノードが持つ値の最大値 ($\mathrm{Max}$) $\rightarrow$ 左右の子の $\mathrm{Max}$ と「自身が持つ値」の最大値から計算可能

2 双対セグメント木

先ほどと同様の構造の木に対して似たような操作をすることで一点取得/区間更新という別のタイプのセグメントツリーを構築することができます。

双対セグメント木のノードには、集約の代わりに評価値を持たせます。ある値に評価値を反映させる計算を評価と呼び、可換モノイド(評価順を入れ替えても同じ結果になるもの)を評価に採用できます。はじめ、全てのノードには評価の単位元 (ある値に評価しても値が変化しないもの) を持たせておきます。

2.1 区間更新

双対セグメント木で区間更新を行う際も、通常のセグメント木の区間取得と同様に区間に対応するセグメントを選択します。列の区間内の要素を全て更新する代わりに、選択したセグメントに区間を代表して更新をかけます。

今回の例は一点取得/区間加算タイプです。選択したセグメントにのみ評価を加算し、他のセグメントは見ないことで区間加算の計算量を $O(\log{(区間幅)})$ 時間で抑えています。

また、評価はモノイドなので複数の区間加算の結果を結合して保持することができます。以下の図はさらに $+4$ の区間加算を行う様子です。

2.2 一点取得

列の一点を取得は、その一点をカバーするセグメントが持つ評価値を全て評価 (結合) したものを計算することで処理できます。

上記の例では $7$ に $0,4,0$ を順に評価します。今回の評価は加算なので、結果は $(((7+0)+4)+0) = 11$ です。

3 遅延評価セグメント木

先の $2$ 種類のセグメント木は、値の集約 と 値の評価 のどちらか片方のみを持つセグメント木でした。それに対して遅延評価セグメント木は、値の集約 と 値の評価 の両方を持つセグメント木です。遅延評価セグメント木は区間取得/区間更新タイプのセグメント木で、多くの場合は先に紹介した $2$ 種類の上位互換として機能します。

今回は区間和/区間加算をサポートする場合を例に挙げて考えます。基本的な構造は通常のセグメント木と同じですが、評価の扱いを少し変えて遅延評価 (下図においては括弧内の値) として保持します。

3.1 区間更新

以下のように、区間 $[0,6)$ に一律に $-5$ 加算する場合の処理を見てみましょう。

双対セグメント木のように、評価を保持する代表セグメントを選択し、それらのセグメントに評価を遅延評価として乗せることで解決を図ります。

その後、セグメントが持つ集約値を評価する必要があります。この場合、集約値は左右の子ノードの集約値から再計算することはできず、セグメントが持つデータ と 遅延評価の値 から正しい集約値を 再計算 できる必要があります。

今回は集約が区間和、更新が区間加算なので、元の集約値に $セグメントの幅 \times 評価値$ を加算することで、セグメント自身が持つ値のみから正しい集約値を再計算することができました。

しかし、遅延評価セグメント木の区間加算には双対セグメント木の場合とは決定的に異なることがあります。今、加算する区間を代表するセグメントに評価を反映することには成功しました。しかし今回のセグメント木では、更新する区間と重複部分があるセグメント全てに対して評価を反映する必要があります。

上記のピンクで塗られたセグメントの集約値には、区間加算の結果が反映されていません。このピンクのセグメントのうち、上側と下側で別の処理を行うことで、セグメント木全体に評価を行き渡らせます。

3.1.1 上側部分の評価

区間更新を反映 (集約を再計算) したセグメントを末端として、木 DP の要領で部分木の集約を再計算して行きます。評価する区間を代表して選択したセグメント (赤枠のセグメント) の評価は終わっているので、上側のセグメントに関しては左右の子を見ることで集約を正しく再計算できます。

3.1.2 下側部分の評価

集約の再計算の際に解消した遅延評価を、そのまま左右の子ノードにかけます。これを評価の伝播と言います。

この処理を行なっても依然として下側のセグメントは未評価のままですが、この部分の評価は必要になるまで遅延させておいても良いです。要するに、評価が行われていないセグメントは、次にそのセグメントにアクセスされるまで正しい集約値を持たないことになります。

3.2 遅延評価の伝播

セグメントへのアクセスは根から探索して行うので、その道中で未評価の評価を実行&子ノードに降ろすことで、アクセスの道中のついでに先ほどの区間の下側セグメントに評価が行き渡ります。要素アクセス時に根からの探索順でこの処理を行うので、セグメントにアクセスしたタイミングで正しい集約値が再計算されていることが保証されます。

区間取得や区間更新の際も同様です。正しく評価が伝播及び評価されていれば、区間取得で得る値もちゃんと更新クエリが反映されたものになります。

3.3 遅延評価のマージ

遅延評価が結合可能であることに注目すると、複数の区間更新クエリの評価値を溜めておいて、必要なタイミングで一気に反映させることができます。

今回の評価は加算なので、新たに評価が加わった際は元々存在した遅延評価に加算してから評価すれば良いです。もちろん上側/下側のセグメントの評価も行います。

評価と集約はそれぞれモノイドであれば OK ですが、同時に計算可能かどうかはまた別の問題なので注意が必要です。

3.4 遅延評価の例 (アフィン変換)

$\mathrm{affine}(x,a,b) := ax + b$ を、$x$ に対するアフィン変換 $(a,b)$ と定義します。アフィン変換を遅延評価にすることで区間内の要素全てにアフィン変換を行うことができます。この記事で紹介した区間加算の遅延評価は、アフィン変換の特殊な場合です ($b$ 加算は、$(1,b)$ と同じ)。また、区間内の値を全て $x$ にする区間代入は、$(0,x)$ の区間アフィン変換と同じです。

$x$ に対するアフィン変換 $\mathrm{affine}(x,a,b)$ は、$2$ つのパラメータ $(a,b)$ で決定されるので、この $(a,b)$ を遅延評価として保持します。既に $(a_1,b_1)$ の遅延評価を持つノードに新たに遅延評価 $(a_2,b_2)$ が加わるとき、二つの遅延評価をマージした $({a_1}{a_2} , {a_2}{b_1} + b_2)$ を新たな遅延評価として保持させることができます。

3.4.1 集約への影響

遅延したアフィン変換 $a,b$ の評価は、ノードが持つ値に対してアフィン変換を適用するだけでなく、ノードが持つ集約値にも適用する必要があります。先述の集約の例について、どのように評価すべきかを説明します。

$\mathrm{Sum}$ に $a\times\mathrm{Sum} + b\times$「セグメントがカバーする区間長」を代入する (区間内要素全てに $b$ 加算するので区間長をかける)
$\mathrm{Min} , \mathrm{Max}$ について
1. $\mathrm{Min},\mathrm{Max}$ にそれぞれ $a\times\mathrm{Min} + b$ と $a\times\mathrm{Max} + b$ を代入する。
2. アフィン変換後、$\mathrm{Max} \leq \mathrm{Min}$ なら、$\mathrm{Min}$ と $\mathrm{Max}$ を入れ替える ( $a$ の符号の影響 )。
$\mathrm{Min} , \mathrm{Max}$ のどちらか一方しか集約しない場合はアフィン変換を行えないことに注意してください。

4 動的セグメント木

通常のセグメント木では初期状態の数列が与えられていたため、セグメント木全体でカバーする範囲が $[0,数列サイズ)$ 程度でした。

動的セグメント木では、初期状態として区間 $[\mathrm{Lmost},\mathrm{Rmost})$ と初期値 $\mathrm{iv}$ が与えられます。この時、動的セグメント木は、定義域が $[\mathrm{Lmost},\mathrm{Rmost})$ であり、$\mathrm{iv}$ で初期化された列を表現します。動的セグメント木の利点として、定義域 $[\mathrm{Lmost},\mathrm{Rmost})$ が巨大な場合や、負の領域である場合にも対処できることがあります。

4.1 表現

動的セグメント木では、各セグメントは数列の要素を表現する値 $\mathrm{V}$ と集約 (今回は $\mathrm{Sum}$) を持ちます。ただし、通常のセグメント木と同様に、数列の要素を表現する $\mathrm{V}$ は末端セグメントのみ有効なものとして問題ありません。ただし、動的セグメント木における末端セグメントとは、左右の子の少なくとも一方が存在しないセグメントを指します。

$[\mathrm{Lmost},\mathrm{Rmost})$ をカバーするセグメント木のセグメントを全て構築してしまうと、$O(\mathrm{Rmost}-\mathrm{Lmost})$ 個のセグメントが必要になってしまいます。そこで、動的セグメント木の初期状態では区間 $[\mathrm{Lmost},\mathrm{Rmost})$ をカバーする根のみを管理します。

例えば上の図は、区間 $[0,9)$ を $\mathrm{iv} = 3$ で初期化した動的セグメント木です。根以外のノードはまだ生成されていません。セグメントの左右の子がまだ生成されていない場合、それらの集約から自身の集約を計算できないので、集約 $\mathrm{Sum}$ を自身がカバーする範囲と自身が持つ値 $\mathrm{V}$ から計算する必要があります。

動的セグメント木の末端セグメントは、そのセグメントに対応する区間内の要素が全て $\mathrm{V}$ であることを示します。例えばこの動的セグメント木は数列 $\{3,3,3,3,3,3,3,3,3\}$ を表現しています。

4.2 頂点の動的確保

動的セグメント木も通常のセグメント木のように、セグメントをうまく選択することでデータの取得を行います。動的セグメント木ははじめから全てのセグメントを明示的に用意しているわけではないので、必要なセグメント及びそのセグメントにアクセスするパスを動的に確保する必要があります。

例として、区間 $[0,6)$ に区間更新を行う場合を示します。以下の図は、区間 $[0,6)$ にアクセスするために根の左右の子を確保する様子です。このとき、根が持つ値 $\mathrm{V}$ を左右の子に継承します。また、根が末端でなくなったので今後は根に対して $\mathrm{V}$ を考える必要が無くなりました。

根は区間 $[0,9)$ に対応しているので、これを半分程度に分割して左右の子セグメントとします。新たに確保した左右の子は、自身が持つ集約 $\mathrm{Sum}$ を自身が持つ情報から計算する必要があります。

根の左に確保した子は区間 $[0,4)$ に対応しており、これは更新を行う区間 $[0,6)$ にすっぽり含まれるため、これ以上分割を行う必要はありません。それに対して右の子はまだ $[0,6)$ からはみ出る部分があるため、新たに子を動的確保します。

これで目的の区間 $[0,6)$ をちょうどカバーするセグメントが生成されたので、これらに対して遅延評価を乗せます。その後、上側の集約を再計算するために自身の集約値を再計算し、遅延評価を解消します。

遅延評価を解消した後は上側のセグメントの集約を再計算し、下側にも評価を伝播させる必要があります。ところが、今回はまだ下側のセグメントが確保されていないので、遅延評価は解消させてかまいません。末端セグメントは、それに対応する区間内の要素全てが同じ値を持つことを示しているため、末端セグメントの $\mathrm{V}$ さえわかっているなら、それよりも下のセグメントの情報は不要なのです。

以下は区間 $[2,9)$ にさらに区間更新を行う様子です。

集約の再計算、遅延評価の伝播を同様に行います。先ほどと異なる点として、今回は遅延評価の伝播先のセグメントが存在しているので、ちゃんと遅延評価を伝播させる必要があります。

4.3 要素アクセス (メモリの節約)

動的セグメント木では、値の更新を伴う場合以外で頂点の動的確保を行う必要はありません。末端セグメントは同じ値を持つ区間を表すので、要素アクセス時に末端セグメントに到達した時点で、アクセスしたい値や集約が何であるかを逆算可能なのです。

例えば区間取得の場合、上図のように末端セグメントをうまく切り取って、計算用の一時的なセグメントを生成することで、新たに子を動的確保しなくても区間をカバーするセグメントを得ることができます。

動的セグメント木のノードは、区間幅などのデータから自身の集約を逆算可能なはずなので、上記の手段は有効であることが保証されています。なお、生成した一時的なセグメントを計算終了後に破棄することで、メモリの節約にもなります。

4.3.1 空間計算量と注意

長さ $N$ の列を表現する通常のセグメント木の頂点数が $O(N)$ 個であることに対し、アクセス可能な index が $[\mathrm{Lmost},\mathrm{Rmost})$ である列を表現する動的セグメント木は、$Q$ 回の更新クエリに対して $O(Q\log{(\mathrm{Rmost}-\mathrm{Lmost})})$ 個の頂点が必要になります。

このように、動的セグメント木においては通常よりもメモリの制約が強いことに注意する必要があり、前節のような小さい工夫も積極的に採用していく必要があります。

4.3.2 V について

ここまでで、セグメント木のノードは値 $\mathrm{V}$ をもつと説明しましたが、実は集約値から $\mathrm{V}$ を逆算することで、$\mathrm{V}$ を明示的に持たなくて良くなる場合もあります。

子の動的確保におけるメモリ節約のために片方の子のみ確保するなどの工夫がある場合を除いて、全てのノードは「子が存在しない」か「左右の両方の子が存在する」のいずれかの場合しか考える必要はありません。ここで、$\mathrm{V}$ が意味を持つのは末端の (子が存在しない) セグメントのみです。このようなセグメントに対応する区間内の要素は全て同じ値を持つはずなので、$\mathrm{V}$ を明示的に持たなくても、$\mathrm{Max}$ や $\frac{\mathrm{Sum}}{区間長}$ によって逆算可能です。

ただし、$\mathrm{Max}$ から逆算する場合、アフィン変換が必要な場合に $\mathrm{Min}$ も同時に必要というデメリットがあり、$\mathrm{Sum}$ を用いる場合、値が剰余環 (いわゆる $\mathrm{modint}$) の場合に $0$ 徐算が発生する可能性があります。

5 セグメント木上の二分探索

区間の片方の端を固定したとき、他方の端としてあり得る領域を「条件を満たさない領域」と「条件を満たす領域」に二分することを考えます。例えば、以下は区間の左端 $L$ を固定したときに、区間内要素の総和が $9$ 以上であるかどうかで右端 $R$ の領域を分割した様子です。

このような領域の分割を、以下のパラメータを用いて抽象化することができます。ただし、このパラメータは区間の左端を固定する場合のものです。

$L := $ 区間の左端の index
$Rlim := $ $R$ として許容する上限値
$Eq := $ 区間内の要素を集約するモノイドの単位元
$op(a,b) := $ 区間内の要素を集約するモノイドの二項演算
$judge(x) :=$ $op$ による区間の集約値 $x$ が、条件を満たすかどうかを bool で返す関数

このようなパラメータに対して、領域の境界をセグ木 $S$ 上で愚直に二分探索してしまうと、二分探索のイテレーション $O(\log{(数列サイズ)})$ 回それぞれの区間取得に $O(\log{(数列サイズ)})$ 時間かかってしまい、$\log$ に二乗がついてしまいます。

そこで、セグメント木のセグメントがうまく分割統治を行っていることを利用します。二分探索のイテレーションでアクセスする地点をセグメントの端点に一致させることで、区間の集約の取得にかかる $\log$ を一つ落とすことができます。

5.1 アルゴリズム

まず、固定する左端 $L$ から $Rlim$ までの区間をセグメント木から選択して、それらを左から順に格納した列を $\mathrm{bucket}$ とします。またそれと同時に、$judge(x)$ で使用する種類の集約を $\mathrm{bucket}$ に格納された先頭のセグメントから累積させる形でメモしておきます。今回の例では $\mathrm{Sum}$ を扱うので累積和を管理します。

$L$ から列の $Rlim$ までの集約がはじめから条件を満たさないならば、全ての領域で条件を満たさないとして終了します。以降は選択した区間を $[L,R)$ として、$[L,R)$ が条件を満たすように範囲を狭めていくことで、条件に関する領域の境界を特定します。

このステップでは、領域の境界が以下の図の赤の領域と黄色の領域のどちらに含まれるかを特定します。

試しに黄色の領域を $\mathrm{bucket}$ から削除してみると、$\mathrm{bucket}$ の最も右のセグメントまでの $\mathrm{prefix\space sum}$ が条件を満たさなくなるので、区間 $[L,R)$ を赤の領域まで狭めることはできず、境界を黄色の領域から探すべきであることが特定できます。すると次に探索すべき領域は黄色のセグメントの左右の子セグメント $2$ つであることがわかります。

探索を続けるために黄色のセグメントを左右の子セグメントで置き換え、このことを $\mathrm{bucket}$ とその累積集約に反映させます。以降も同様に探索すべき領域の特定を進めていきます。

またこの処理では、セグメントの二分割によって区間を狭めていくため、まだ分割されていない区間が存在するならば、それらの二分割を表す 一時的なセグメント を生成して計算を続ける必要があります。

こうして処理を続けた結果、探索するべき領域の長さが $1$ になれば探索を終了します。このとき、$\mathrm{bucket}$ の中身のセグメントは条件を満たすギリギリの区間 $[L,R)$ に対応します。ただし、全ての区間が条件を満たす場合、あるいは全ての区間が条件を満たさない場合にどうするかは定義しておく必要があります。

また、計算に使用した一時的なセグメントを使用後に破棄することでメモリを節約できます。

5.2 活用例 : 順序付き多重集合

整数の集合をプログラムで管理する際、最もシンプルな方法は以下のような配列 $S$ を管理しておくことです。

$S[x]$ := 集合に含まれる整数 $x$ の個数

この配列 $S$ を動的セグメント木で管理します。なお、管理する整数が小さい場合や、あらかじめ座標圧縮できる場合は動的でない通常のセグ木で十分です。

5.2.1 基本機能

まずは順序付き多重集合の基本機能として以下を定義します。

$\mathrm{insert}(x,c) := x$ を $c$ 個追加する。$S[x]$ に $c$ 加算すれば良い
$\mathrm{erase}(x,c) := x$ を $c$ 個削除する。$S[x]$ に $-c$ 加算すれば良い
$\mathrm{lower\_bound}(x) := x$ 未満の要素数。$S[x-1]$ までの prefix_sum (区間取得)
$\mathrm{upper\_bound}(x) := x$ 以下の要素数。$S[x]$ までの prefix_sum (区間取得)
$\mathrm{count}(x) := x$ の個数。$S[x]$ のこと

5.2.2 ランダムアクセス

セグメント木上の二分探索を用いることで、要素へのランダムアクセスを定義できます。

$\mathrm{get(i)} := $ 格納されている要素のうち、昇順で $i$ 番目の要素を取得する。

左端が $\mathrm{Lmost}$ で固定されており、右端の上限が $\mathrm{Rmost}$ である区間で、区間内要素の総和が $i+1$ 以上となる区間の右端の境界 $R$ を二分探索で求めると、$R-1$ が答えになります。(動的セグメント木の index の範囲を $[\mathrm{Lmost},\mathrm{Rmost})$ と定義しています。)

5.2.3 最頻値

多重集合に含まれる要素のうち、最も多く含まれるものを計算できます。

$\mathrm{maximum\_freq}(l,r) := $ $l$ 以上 $r$ 未満の要素の要素で、集合に最も多く登場する要素

$Eq := -\infty$ , $op := max$ とし、定数 $bdr$ を「$l$ 以上 $r$ 未満の要素で、最も多い登場回数」とします。$bdr$ は $[l,r)$ の区間最大値をセグメント木 $S$ から取得することで求まります。ここで、条件 $judge(x)$ を「$\mathrm{bucket}$ 内の最大値 $x$ が $bdr$ 以上である」と定義して二分探索すると、区間の右端 $R$ に対して $R-1$ が答えになります。

この二分探索によって、列 $S$ の $[L,R)$ の要素のうち、最大値がどこに登場するのかを特定することができます。ただし複数存在する場合は、そのうち最小のものを返します。また区間の右端を固定して二分探索をすると、最も大きいものを返します。

5.2.4 個数が最も少ない要素

最頻値の反対もできます。

$\mathrm{minimum\_freq}(l,r) := $ $l$ 以上 $r$ 未満の要素の要素で、集合に格納されている個数が最も少ない要素。ただし、$0$ 個のものも含む。

最頻値と同じような二分探索も可能ですが、セグメント木 $S$ に記録した値の符号を反転 (アフィン変換 $(-1,0)$) することで、最頻値と同じ二分探索に帰着できます。また、$0$ 個のものを含まないようにするためには、$S$ に $0$ の代わりに $\infty$ (符号反転後は $-\infty$) を格納すると良いです。ただし、$\mathrm{insert} , \mathrm{erase}$ の際に処理を場合分けする必要があることに注意してください。

5.2.5 総和の計算

セグメント木の集約として $\mathrm{ProdSum} := \sum{i\times S[i]}$ を定義します。これを用いることで、指定した範囲内の要素の総和を取得できます。

$\mathrm{get\_sum}(l,r) := $ $l$ 以上 $r$ 未満の要素の総和
$\mathrm{range\_sum}(l,r) = $ 格納されている要素を昇順で並べたとき、区間 $[l,r)$ に含まれる要素の総和

5.2.6 セグ木の遅延評価を用いた機能

セグ木の遅延評価を用いることで以下を定義できます (全てアフィン変換の特殊な場合)。

$\mathrm{range\_insert(L,R,c)} := $ $L$ 以上 $R$ 未満の整数をそれぞれ $c$ 個ずつ集合に追加する (区間 Add)。
$\mathrm{range\_erase(L,R,c)} := $ $L$ 以上 $R$ 未満の整数をそれぞれ $c$ 個ずつ集合から削除する (区間 Add)。
$\mathrm{uniform\_insert(L,R,c)} := $ $L$ 以上 $R$ 未満の整数それぞれについて、その整数が集合に含まれる個数を $c$ 個にする (区間 Update)。
$\mathrm{multiple\_insert(L,R,c)} := $ $L$ 以上 $R$ 未満の整数それぞれについて、個数を $c$ 倍する (区間 Affine)。

5.2.7 注意点

std::set などに比べるとかなり重たい上に、メモリも食うので注意。また、気をつけないとすぐにオーバーフローしてしまうことにも注意。

6 多次元セグメント木

長方形や空間などの多次元の領域クエリを処理するセグメント木を紹介します。まず、$N$ 次元の矩形領域に回答するセグメント木を $N$ 次元セグメント木と呼ぶことにします。例えば $2$ 次元セグメント木は $2$ 次元平面のマス目を表現し、$3$ 次元であれば $3$ 次元空間のマス目を表現します。

まず、これまで紹介したセグメント木を $1$ 次元セグメント木と定義します。こうして、$N$ 次元セグメント木を「各セグメントに $N-1$ 次元セグメント木を乗せたセグメント木」と再帰的に定義することにします。

6.1 値の集約

$N$ 次元セグメント木の各セグメントについても集約を定義します。以下の図は $2$ 次元セグメント木において、$y = 0$ を担当する $1$ 次元セグメント木と、$y = 1$ を担当する $1$ 次元セグメント木から、$y$ 軸の区間 $[0,2)$ をカバーする $1$ 次元セグメント木を集約した様子です。

さらに一般化して、二つの $p$ 次元セグメント木 $A,B$ について、それらの集約を以下で定義します。ただし $0$ 次元セグメント木を数値など、マス目に持たせる値と定義します。

$p = 0$ の場合 : $1$ 次元セグメント木のセグメントが持つ値の集約なので、ここでの演算の種類が $N$ 次元セグメント木で計算可能な集約を決定する。今回の例の場合は総和となる。
$p \geq 1$ の場合 : $A,B$ 及び $A,B$ の集約結果 $C$ はいずれも同じ形をした $p$ 次元セグ木である。$C$ の各頂点は、$A,B$ において同じ位置の頂点が持つ $p-1$ 次元セグ木をマージしてできる $p-1$ 次元セグ木を持つ。

このようにして、集約についても $1$ 次元における集約から再帰的に定義できました。

6.2 矩形領域取得

$N$ 次元セグメント木が表現する $N$ 次元空間において、$N$ 次元の矩形 (長方形みたいのもの) 内の要素の集約を取得できます。

$N$ 番目の次元のみに注目すれば、$N$ 次元セグメント木といえども $1$ 次元セグメント木と同じ構造です。よって、$N$ 次元矩形が与えられたとき、$N$ 次元セグ木からは、与えられた矩形の $N$ 番目の次元の区間をカバーするセグメントを得ることができます。

6.2.1 矩形取得の具体的な流れ

矩形の上の次元から、その次元における区間をカバーするセグメントを選択していきます。以下の図は $2$ 次元のマス目から長方形 $[0,2) \times [0,3)$ 内の要素の集約を計算する様子です。

これを一般化して考えると、以下のようになります。

$N$ 次元セグメント木から、与えられた矩形の $N$ 番目の次元の区間をカバーするセグメントを選択する。選択したセグメントは全て $N-1$ 次元セグメント木である。
$1$ で得た $N-1$ 次元セグメント木それぞれに対して、与えられた矩形の $N-1$ 番目の次元の区間をカバーするセグメントを選択する。選択したセグメントは全て $N-2$ 次元セグメント木である。
$2$ で得た $N-2$ 次元セグメント木それぞれに対して、与えられた矩形の $N-2$ 番目の次元の区間をカバーするセグメントを選択する。選択したセグメントは全て $N-3$ 次元セグメント木である。

このように上の次元からセグメントを選択していくと、最終的に $1$ 次元セグメント木からセグメントを選択することになります。こうして得た $1$ 次元セグメント木のセグメントが $N$ 次元矩形を過不足なくカバーしています。これらのセグメントが持つ値を全てマージしたものが、矩形内の要素の集約になります。

6.2.2 計算量

矩形の $p$ 次の区間幅を $L_p$ とすると、$p$ 次セグ木から $O(\log{L_p})$ 個の $p-1$ 次セグ木を取り出し、それら全てに対して、$O(\log{L_{p-1}})$ 個の $p-2$ 次セグ木を取り出し $\dots$ と手続きが進むので、最終的に選択されるセグメントの個数は $O(\prod_{1 \leq p \leq N}{\log{L_p}})$ 個になります。

6.3 値の更新

最後に値の更新を説明します。更新した箇所に関係のある地点が $N$ 次元セグ木の構成を満たすように修正していきます。例えば以下の図は $2$ 次元のマス目の一点を更新した場合です。

更新箇所の値を更新すると、当然そのセグメントが属するセグメント木の上部のセグメントの集約を更新する必要があります。すると、次元が低いセグメント木に変更が加わったことにより、それより高次元のセグメント木にも変更を加える必要があります。実際、図からは、更新の影響が $1$ 次元セグメント木の部分と $2$ 次元セグメント木の部分の両方に作用していることがわかります。実は、$N$ 次元セグメント木の更新の手続きは、$N$ 次における影響と、$N-1$ 次以下の部分における影響を別で考えることで楽に実装することができます。

まず、$N$ 次における影響があるセグメントは全て $N-1$ 次元セグメント木であり、それらの影響箇所の更新は、$N-1$ 次元セグメント木における一点更新なので、再帰的に一点更新の手続きを適用できます。

6.4 実装

ここまで読むと分かる通り、セグメント木はその次元が増えたところで、再帰によって $1$ 次元セグメント木と同等の手続きで処理を行うことができます。実装も軽いです。なお双対セグメント木に対しても同様の議論で多次元化できます。

7 セグメント木の永続化

セグ木に対して、更新前のデータを旧バージョン、更新後のデータを新バージョンと呼ぶことにします。セグメント木を永続化することで、更新を行った後からでも過去のデータにアクセスすることができます。また、今回扱うデータ構造のように過去のデータから新バージョンを作ることができるデータ構造を全永続(完全永続)データ構造と言います。

7.1 動的セグメント木の全永続化

動的セグメント木の初期状態を Ver.0、表現する列を $S^{(0)}$ として、動的セグメント木を全永続化します。

冒頭で説明した通り、永続データ構造では更新によるデータの変更を新バージョンの生成と捉えます。また、データ更新前のデータ (過去のバージョン) に自由にアクセスすることができます。

新バージョンをコピーで愚直に生成するのは当然計算量的にありえないので、新バージョン生成の見方を変えて、データ自体のコピーを行うのではなく、データにアクセスするインターフェースのコピーを行うことにします。セグメント木の構造においては、インターフェースが省メモリであるという点で永続化との相性が良いのです。

7.2 根によるバージョン管理

セグメント木の根は全体へのアクセスをもつインターフェースなので、根をコピーすることでバージョンの複製をすることにします。ただし全く同じものを作っても意味がないので、根以外にもデータの変更による影響があるセグメント及び、それらへのアクセスに必要なセグメントをコピーします。

以下の図は、変更したデータへのアクセスに関する部分だけをインターフェースとしてコピーすることで、Ver.0 から Ver.1 を生成した様子です。旧バージョンの根から更新したい要素までの経路を取得し、その経路上のセグメントをコピーして新バージョンとしています。ただし、アクセスする要素までの経路を得るための動的確保は新バージョンで行ってください。

セグメント木においては根から探索して要素にアクセスするので、アクセスするバージョンを指定することは、探索を開始する根のバージョンを指定することです。初回の更新では単に新しいセグ木が生えたようになるのであまり実感が湧きませんが、実際、Ver.0 の根からは Ver 0 の列要素を取得でき、Ver.1 の根からは Ver.1 の列要素を取得できることは確認できます。

7.3 参照の複製によるコピー省略

Ver.1 に新たに変更を加えてみましょう。以下では新たに一点を更新し、更新の影響がある部分を新バージョンのインターフェースとして作成しています。このとき、コピー元 (Ver.1) の根からの同じ探索ルート上に存在するノードを、新バージョンに参照関係ごとコピーし、新バージョンのノード間には新たに参照関係を張り直します。また、コピー元 (Ver.1) のに存在していなかった頂点については、新バージョン (Ver.2) で新たに動的確保されています。

このとき、経路上のコピーしたセグメントは、集約の再計算と無関係な部分についてはコピー元と同じセグメントを参照します。こうすることで集約の再計算、すなわち更新の影響を受けない範囲のコピーを省略することができるため、新バージョンの作成のコストは時間/空間ともに値の更新の影響箇所の個数程度となります。

なお、新たなバージョンの生成によって参照関係が増えるので、全永続動的セグメント木のセグメントには親セグメントへのポインタを持たせません。よって通常のセグメント木のようにデータ更新後に親へのポインタを辿って上側のセグメントの集約を計算することはできません。値の更新時の探索順を一時的に管理して集約を計算する必要があります。

新バージョンのデータも変更があった場所以外は過去のバージョンと同じです。新たに生成した部分以外は過去のバージョンのセグメントを参照することで、新バージョンの根からの探索でも過去のデータに行き着くことができるため、変更がない箇所のデータを使い回すことができるのです。例えば以下の図は Ver.2 のデータ $S^{(2)}$ における区間にアクセスする様子ですが、実際は Ver.2 のインターフェースから参照を辿って $S^{(1)}$ と同じデータにアクセスしていることが確認できます。

また、以下は Ver.2 から新たに Ver.3 を作成する様子です。Ver.3 の根から更新を行う要素までの経路を構築し、それをコピーして Ver.2 のインターフェースとします。以下の例のようにセグメントの参照がバージョンをまたぐ場合、さらに過去のバージョンのセグメントがコピーされることになります。

なおこれまで示した様子を見ると、新バージョン作成時や要素アクセス時に、過去のバージョンの木の構造に変化がないことが確認できます。新バージョン作成時に過去の木の構造を変更する実装方法もありますが、ここでは「データの変更」=「新バージョンの作成」という永続データ構造の説明とマッチする方針をとっています。メモリ効率、直感、実装のしやすさなどを考えると、どのような方針を取るかは割とバリエーションがある印象です。

7.4 メモリに配慮した戦略

ここでは、一度のバージョンアップで複数箇所を更新したい場合を考えます。実行したい更新クエリが以下の形式のデータの集まり $Qr$ として与えられます。

$\{ i , x \} := $ index が $i$ の要素は $x$ である。

一回の更新で約 $\log{(数列サイズ)}$ 個のセグメントがコピーされてしまうので、これら $|Qr|$ 個のデータを一つずつ反映していくと、全体で生成されるコピーが大きくなってしまいます。

これはメモリの無駄遣いなので、一つ更新するごとにコピーを生成するのをやめます。全ての更新を行なった後、その影響があった部分を全て一度にコピーすることで、コピーのサイズを減らすことができます。この戦略の効果は更新を行う index の分布に影響を受けますが、一般には $|Qr|$ が大きいほど有効と考えて良いでしょう。

以下は Ver.2 の複数箇所を変更する様子です。過去のバージョンから分岐して新バージョンを作成する例でもあります。

$\{ i , x \}$ の情報を $i$ の昇順にソートし、$i$ が小さい順に対応するセグメントを訪れる DFS を行うことで、影響がある部分を重複なく取得できます。またこの道中で集約の計算などを行います。

動的セグ木の章で触れたように、動的セグ木においてはメモリ節約の工夫が非常に大切であり、永続化した動的セグメント木においてはより顕著になります。

7.5 区間アクセス

区間管理のための共通化として、以下のメソッド $\mathrm{RangeDFS}(l,r,v)$ を定義します。

$\mathrm{RangeDFS}(l,r,v) :=$ 区間 $[l,r)$ をカバーする最小個のセグメントを $v$ で指定したバージョンの根から探索する。その探索ルート上のセグメントのうち、区間 $[l,r)$ と重複部分があるセグメントを参照関係ごとコピーし、左優先 DFS 順で並べて返す。
- 値の更新の場合と同様に、コピーしたセグメント間のみ参照関係を張り直しておく。
- $v$ で指定した根から到達できないセグメントは、コピーしたセグメントの子として動的確保しておく。
- $\mathrm{RangeDFS}$ によって生成されたセグメントが全て返り値に含まれるとは限らない。

例えば以下の図は Ver.2 の区間を取得する場合です。この場合、$\mathrm{RangeDFS}$ は図のオレンジ色で塗りつぶされたセグメントとオレンジ枠のセグメントを、左優先の DFS 順で返します。

こうして得たセグメントのうち、オレンジ色で塗りつぶされたセグメントの集約値をマージすることで区間和の計算などを行うことができます。なお区間和の計算など、計算のためのデータを取得するために $\mathrm{RangeDFS}$ を行った場合、計算後に $\mathrm{RangeDFS}$ で得たセグメントを破棄することでメモリを節約することができます。

7.6 遅延評価

全永続化していても、遅延評価によって区間更新を行うことができるのでしょうか。全永続セグ木の方針が更新による影響部分を新バージョンに新規作成することなので、区間更新の影響部分を全てコピーすると計算量が悪化してしまいます。ところが、遅延評価を加えたセグメントよりも下のセグメントのコピーの生成は、実際に遅延評価を評価するタイミングまで遅延させることができるので、実際に新規作成するセグメントの個数は、区間取得と同程度になります。

以下の図は Ver.1 に区間加算を行い、Ver.5 を作成する様子です。更新をかけたい区間を $\mathrm{RangeDFS}$ で取得し、オレンジ色で塗りつぶされたセグメントに遅延評価を載せます。このとき、$\mathrm{RangeDFS}$ で得たものを新バージョン (Ver.5) とします。

その後これまでのセグメント木と同様に、まずは乗せた部分の遅延評価を解消し、上側のセグメントの集約値を再計算します。

次に下側に遅延評価を伝播させる必要があります。今回のように伝播先が過去のバージョンのセグメントを参照している場合、過去のバージョンに遅延評価を伝播させるわけにはいかないので、参照しているセグメントを自身と同じバージョンの子セグメントとして新たにコピーし、新たにコピーしたものに遅延評価を伝播させます。(これまでと同様に参照関係を含めてセグメントをコピーします。)

ここで、遅延評価を新たに乗せるのは最新バージョンのみであることと、全ての要素アクセスはいずれかの根から探索して行うことから、同バージョンの子セグメントに遅延評価を伝播するような状況にはならないことが保証されています。

さらに Ver.5 に区間更新を行い、Ver.6 を作成してみましょう。以下の図では Ver.6 の根の左の子が Ver.5 のセグメントを参照した状態ですが、その状態のまま遅延評価が加わります。

この図からも冒頭で説明した通り、遅延評価を加えたセグメントよりも下のセグメントのコピーの生成が、実際に遅延評価を評価するタイミングまで遅延されることがわかります。

また一度バージョンが作成されると、そのバージョンのデータは「木の構成」,「遅延評価の状態」を含めて後から変更されない方針をとっています。これも先述の通り「データの変更」=「新バージョンの作成」という永続データ構造の説明に沿った方針をとっています。

遅延評価の伝播が起こるのは、$\mathrm{RangeDFS}$ などで生成されたコピーに対してのみです。例えば以下は遅延評価をもつバージョン (Ver.6) に $\mathrm{RangeDFS}$ を行い、遅延評価を伝播させながら区間を取得する様子です。

何度も強調していますが、このように遅延評価,頂点の動的確保は $\mathrm{RangeDFS}$ などで新たに確保されたコピー生成時にのみ実行されます。このようにして、過去のバージョンへの変更を一切許さない方針をとっています。

以下では区間和の取得のために遅延評価を解消していますが、区間取得などにおける $\mathrm{RangeDFS}$ の役割は使用後に破棄する一時的なバージョンの生成なので、どれだけ遅延評価の伝播や頂点の動的確保を行っても構いません。

7.7 区間コピー

永続データ構造において、あるバージョンのある区間を、別のバージョンの同じ位置に貼り付けたものを新バージョンとして作成することができます。ただし残念ながらセグ木の永続化ではかの有名な「コピー&ペースト」は解けないので注意です。

まず、区間をコピーするバージョンのその区間に対して $\mathrm{RangeDFS}$ で生成したものを新バージョンとします。以下の図の場合は Ver.6 の区間をコピーして Ver.7 としています。また、コピーを貼り付けるバージョンに対しても $\mathrm{RangeDFS}$ でコピーを生成しておきます。

新バージョンは確かにコピーした区間を参照できていますが、それ以外の地点も参照しています。コピーしたい区間以外は、貼り付けたいバージョンを参照するようにしたいです。

そこで新バージョンにおいて、コピーする区間と重ならないセグメントへの参照を、$\mathrm{RangeDFS}$ で生成したもう一つのコピーの同じ位置のセグメントに張り替えることにします。以下の図は、Ver.7 においてコピーする区間と被らないセグメントへの参照を $\mathrm{RangeDFS(v2)}$ の同位置のセグメントに張り替える様子です。

その後、Ver.7 の張り替えた参照より上のセグメントに対して、集約の再計算を行う必要があります。また新たに作成したノードのうち Ver.7 から到達できないものやどこからも参照されなくなったノードを破棄することで、メモリを節約することができます。

図からも Ver.7 が Ver.2 に Ver.6 の区間を貼り付けたものであることが確認できます。

7.8 メモリ効率化

永続セグ木のメモリ効率のボトルネックになるのは、やはりノードを表現するデータです。この記事で紹介したセグメント木を表現するためには、それぞれのノードには少なくとも以下のデータが必要です。

左右の子へのポインタ
区間を表す $2$ つの整数
総和を表す値 $\mathrm{Sum}$ (自分は他にも $\mathrm{Min},\mathrm{Max},\mathrm{ProdSum}$ を定義)
遅延中のアフィン変換を表す $2$ つの値 $(a,b)$
自身がどのバージョンかを表す整数

自分はこれらに加えて bool 変数をたった $1$ つだけ持たせていたのですが、その $1$ つの bool の有無でメモリ上限制限にかかるかどうかが変わるほどの違いが出ました。これはメモリアライメントによる違いであり、bool 変数 $1$ つの差で実際は $8$ byte の差が出ていました。

永続セグ木のメモリ効率化はすればするだけいいんだから！

8 まとめ

今回の記事では、通常のセグメント木から始まり、双対、遅延評価、動的、二分探索、多次元と続けて説明し、最終的な終着点として永続化したセグメント木を説明しました。二分探索で紹介した多重集合は容易に全永続化できますし、動的セグメント木を遅延評価をなくせば多次元化することもできます(メモリ効率が悪すぎて使えませんが)。

このようにこの記事で紹介できていないテクニックもたくさんあるので、興味があればまたぜひ調べてみると良いでしょう。また、亜種としてクエリの時系列ををセグ木の構造で分割統治するテクニックや区間に辺を張るテク、マージソートツリー、Li-Chao Tree、Beats などのテクニックなどもたくさんあります。気が向いたら追記するかも？(おわり)

ソースコード

使い方は後述します。あとコメントの英語が拙いのは気にしないでください。雰囲気がわかればいいのです。

ライセンスは守ってくださいね (このライブラリの冒頭に以下を書くだけで良いです)。

ライセンスに従わない利用を確認した場合、ライセンスに従わない利用をやめるよう指示するなどの処置を取る場合があります。

#include<vector>
#include<unordered_map>
#include<cassert>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<deque>
#include<stack>
#include<sstream>
#include<numeric>
#include<functional>

using std::pair;
using std::deque;
using std::stack;
using std::function;
using std::cout;
using std::ostringstream;
using std::numeric_limits;
using std::endl;
using std::cerr;
using std::min;
using std::max;
using std::swap;
using std::reverse;
using std::string;
using std::vector;
using std::unordered_map;

template<typename index_int , typename T>
struct PersistentDynamicSegmentTree{
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
    inline static const long long FIRST_VERSION = 0;
    inline static const long long ONETIME_VERSION = -1;
    struct Node{
        Node* left = nullptr;
        Node* right = nullptr;
        enum ChildValidation{INVALID , NOCHILD , BOTH};
        inline constexpr ChildValidation valid_check_child(){
            if(this->left == nullptr && this->right == nullptr)return NOCHILD;
            if(this->left != nullptr && this->right != nullptr)return BOTH;
            return INVALID;
        }
        int node_version;
        const index_int rangeLeft , rangeRight;
        inline constexpr index_int range_length()const{return (this->rangeRight - this->rangeLeft);}
        inline constexpr index_int range_mid()const{return ((this->rangeLeft+this->rangeRight)>>1);}
        T Sum, Max, Min;
        T ProdSum;
        inline static const pair<T,T> eq_affine = {T(1),T(0)};
        pair<T,T> lazy_affine = eq_affine;
        inline void set_lazyAffine(T a, T b){
            this->lazy_affine = {a*this->lazy_affine.first , a*this->lazy_affine.second + b};
        }
        private:
        Node(const Node& p) = default;
        public:
        Node(Node&& p) = default;
        Node(){}
        Node(const Node& nd , int ver) : Node(nd) {
            node_version = ver;
        }
        Node(index_int l , index_int r , T x , int ver) : rangeLeft(l) , rangeRight(r) , node_version(ver){
            Max = x;
            Min = x;
            Sum = range_length()*x;
            ProdSum = (x*((rangeRight-1)*rangeRight-(rangeLeft-1)*rangeLeft))/T(2);
        }
        void NodeUpdate(){
            ChildValidation c_state = this->valid_check_child();
            assert(c_state != INVALID);
            if(range_length() == 1){
                Sum = Min = Max;
                ProdSum = Max*rangeLeft;
                return;
            }
            assert(c_state != NOCHILD);
            this->eval(false,false);
            this->left->eval(false,false);
            this->right->eval(false,false);
            this->Sum = this->left->Sum + this->right->Sum;
            this->Min = min(this->left->Min, this->right->Min);
            this->Max = max(this->left->Max, this->right->Max);
            this->ProdSum = this->left->ProdSum + this->right->ProdSum;
        }
        void eval(bool make_child , bool inplace_forced){
            if(!make_child)assert(!inplace_forced);
            ChildValidation c_state = this->valid_check_child();
            assert(c_state != INVALID);
            if(this->lazy_affine != eq_affine){
                this->Min = this->lazy_affine.first * this->Min + this->lazy_affine.second;
                this->Max = this->lazy_affine.first * this->Max + this->lazy_affine.second;
                this->Sum = this->lazy_affine.first * this->Sum + this->lazy_affine.second * this->range_length();
                this->ProdSum = this->lazy_affine.first * this->ProdSum + ((this->lazy_affine.second*((rangeRight-1)*rangeRight - (rangeLeft-1)*rangeLeft))/T(2));
                if(this->Max < this->Min)swap(this->Max,this->Min);
                if(this->valid_check_child() == BOTH){
                    assert(this->node_version != this->left->node_version && this->node_version != this->right->node_version);
                    this->left = new Node(*(this->left),this->node_version);
                    this->right = new Node(*(this->right),this->node_version);
                    this->left->set_lazyAffine(this->lazy_affine.first,this->lazy_affine.second);
                    this->right->set_lazyAffine(this->lazy_affine.first,this->lazy_affine.second);
                }
                this->lazy_affine = eq_affine;
            }
            if(this->range_length() <= 1 || make_child == false)return;
            if(c_state == BOTH && inplace_forced == false)return;
            if(c_state == BOTH && inplace_forced){
                if(this->node_version != this->left->node_version)this->left = new Node(*(this->left),this->node_version);
                if(this->node_version != this->right->node_version)this->right = new Node(*(this->right),this->node_version);
                return;
            }
            assert(c_state == NOCHILD);
            this->left = new Node(this->rangeLeft,this->range_mid(),this->Max , this->node_version);
            this->right = new Node(this->range_mid(),this->rangeRight,this->Max , this->node_version);
        }
    };
    inline static bool cover(index_int l , index_int r , index_int i){
        return bool(l <= i && i < r);
    }
    inline static bool intersect(index_int l1 , index_int r1 , index_int l2 , index_int r2){
        return bool(l1 <= l2 && l2 < r1) || bool(l2 <= l1 && l1 < r2);
    }
    inline static index_int CommonArea(index_int l1 , index_int r1 , index_int l2 , index_int r2){
        if(!intersect(l1,r1,l2,r2))return 0;
        return min(r1,r2) - max(l1,l2);
    }
    private:
    index_int _Llim,_Rlim;
    const T init_value;
    vector<Node*> m_RootVersion;
    vector<vector<int>> update_flow = {{}};
    Node* m_OneTime_root = nullptr;
    void FreeOneTimeVersion(){
        if(m_OneTime_root == nullptr)return;
        stack<Node*> st;
        st.push(m_OneTime_root);
        while(!st.empty()){
            Node* now = st.top();
            st.pop();
            assert(now->node_version == ONETIME_VERSION);
            if(now->valid_check_child() == Node::BOTH){
                if(now->left->node_version == ONETIME_VERSION)st.push(now->left);
                if(now->right->node_version == ONETIME_VERSION)st.push(now->right);
            }
            delete now;
        }
        m_OneTime_root = nullptr;
    }
    vector<Node*> RangeDFSRoute(index_int l , index_int r , Node* rt){
        assert(rt->node_version == ONETIME_VERSION || rt->node_version > this->version());
        vector<Node*> res;
        stack<Node*> st;
        st.push(rt);
        while(!st.empty()){
            Node* now = st.top();
            assert(now->node_version == rt->node_version);
            assert(intersect(l , r , now->rangeLeft , now->rangeRight));
            st.pop();
            res.push_back(now);
            if(now->range_length() == 1 || CommonArea(l, r, now->rangeLeft , now->rangeRight) == now->range_length())continue;
            assert(now->range_length() >= 2);
            now->eval(true,bool(now->valid_check_child() == Node::NOCHILD));
            if(intersect(l,r,now->rangeLeft , now->range_mid())){
                if(now->left->node_version != rt->node_version)now->left = new Node(*(now->left) , rt->node_version);
                st.push(now->left);
            }
            if(intersect(l,r, now->range_mid() , now->rangeRight)){
                if(now->right->node_version != rt->node_version)now->right = new Node(*(now->right) , rt->node_version);
                st.push(now->right);
            }
        }
        return res;
    }
    vector<Node*> RangeOneTimeSegments(index_int l , index_int r){
        vector<Node*> dfs_route = RangeDFSRoute(l,r,m_OneTime_root);
        vector<Node*> res;
        for(Node* seg : dfs_route){
            assert(seg->node_version == ONETIME_VERSION);
            if(CommonArea(l,r,seg->rangeLeft,seg->rangeRight) != seg->range_length())continue;
            seg->eval(false,false);
            res.push_back(seg);
        }
        return res;
    }
    inline static void operate_update(T& a, T b){a = b;}
    inline static void operate_add(T& a , T b){a += b;}
    template<void (*upd)(T&,T)>
    void version_update(vector<pair<index_int,T>> queries , int ver){
        assert(ver != ONETIME_VERSION);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        sort(queries.begin(),queries.end(),[&](pair<index_int,T> a , pair<index_int,T> b){return bool(a.first < b.first);});
        Node* now = new Node(*m_RootVersion[ver] , m_RootVersion.size());
        m_RootVersion.push_back(now);
        deque<Node*> path;
        path.push_back(now);
        for(pair<index_int,T> q : queries){
            assert(Llimit() <= q.first && q.first < Rlimit());
            while(cover(now->rangeLeft,now->rangeRight,q.first) == false){
                path.back()->NodeUpdate();
                path.pop_back();
                now = path.back();
            }
            while(now->range_length() > 1){
                now->eval(true,false);
                assert(now->valid_check_child() == Node::BOTH);
                if(cover(now->left->rangeLeft , now->left->rangeRight , q.first)){
                    if(now->left->node_version != now->node_version)now->left = new Node(*(now->left),now->node_version);
                    path.push_back(now->left);
                }else{
                    if(now->right->node_version != now->node_version)now->right = new Node(*(now->right),now->node_version);
                    path.push_back(now->right);
                }
                now = path.back();
            }
            now->eval(true,false);
            assert(path.back()->range_length() == 1);
            upd(path.back()->Max,q.second);
        }
        while(path.size() > 0){
            path.back()->NodeUpdate();
            path.pop_back();
        }
        memo_versionflow(ver,this->version());
    }
    void memo_versionflow(int i , int j){
        while( update_flow.size() <= max(i,j))update_flow.emplace_back();
        update_flow[i].push_back(j);
    }
    public:
    PersistentDynamicSegmentTree()
        :_Llim(numeric_limits<index_int>::min()/2),_Rlim(numeric_limits<index_int>::max()/2)
            ,init_value(0),m_RootVersion(1,new Node(_Llim,_Rlim,init_value,0)){}
    PersistentDynamicSegmentTree(index_int L_ , index_int R_ , T init_value_)
        :_Llim(L_),_Rlim(R_),init_value(init_value_), m_RootVersion(1,new Node(L_,R_,init_value,0)){}
    ~PersistentDynamicSegmentTree(){}
    PersistentDynamicSegmentTree(const PersistentDynamicSegmentTree &x) = delete ;
    PersistentDynamicSegmentTree& operator = (const PersistentDynamicSegmentTree &x) = delete ;
    PersistentDynamicSegmentTree ( PersistentDynamicSegmentTree&& x){assert(0);}
    PersistentDynamicSegmentTree& operator = ( PersistentDynamicSegmentTree&& x){assert(0);}
    index_int Llimit(){return _Llim;}
    index_int Rlimit(){return _Rlim;}
    int version(){
        return int(m_RootVersion.size()) - 1;
    }
    void update_together(vector<pair<index_int,T>> queries , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        unordered_map<index_int,int> count;
        for(const pair<index_int,T>& p : queries){
            count[p.first]++;
            assert(count[p.first]<=1);
        }
        version_update<operate_update>(queries,ver);
    }
    void update(index_int i , T x , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= i && i < Rlimit());
        update_together({{i,x}},ver);
    }
    void add_together(vector<pair<index_int,T>> queries , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        version_update<operate_add>(queries,ver);
    }
    void add(index_int i , T x , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= i && i < Rlimit());
        add_together({{i,x}},ver);
    }
    void RangeCopy(index_int l , index_int r , int v1 , int v2){
        assert(FIRST_VERSION <= v1 && v1 <= this->version());
        assert(FIRST_VERSION <= v2 && v2 <= this->version());
        assert(Llimit() <= l && l < r && r <= Rlimit());
        Node* v1copy = new Node(*m_RootVersion[v1] , m_RootVersion.size());
        vector<Node*> RangeDFS_v1copy = RangeDFSRoute(l,r,v1copy);
        m_RootVersion.push_back(v1copy);
        m_OneTime_root = new Node(*m_RootVersion[v2] , ONETIME_VERSION);
        vector<Node*> RangeDFS_v2Resource = RangeDFSRoute(l,r,m_OneTime_root);
        for(int i = 0 ; i < RangeDFS_v1copy.size() ; i++){
            Node* new_v_node = RangeDFS_v1copy[i];
            Node* resource_node = RangeDFS_v2Resource[i];
            if(new_v_node->range_length() <= 1)continue;
            if(new_v_node->valid_check_child() == Node::NOCHILD)continue;
            resource_node->eval(true,false);
            assert(new_v_node->rangeLeft == resource_node->rangeLeft);
            assert(new_v_node->rangeRight == resource_node->rangeRight);
            assert(resource_node->valid_check_child() == Node::BOTH);
            if(!intersect(l,r,resource_node->left->rangeLeft,resource_node->left->rangeRight)){
                if(new_v_node->left->node_version == new_v_node->node_version){
                    if(new_v_node->left->valid_check_child() == Node::BOTH){
                        assert(new_v_node->left->left->node_version != ONETIME_VERSION);
                        assert(new_v_node->left->right->node_version != ONETIME_VERSION);
                    }
                    delete new_v_node->left;
                }
                new_v_node->left = resource_node->left;
                if(new_v_node->left->node_version == ONETIME_VERSION){
                    if(new_v_node->left->valid_check_child() == Node::BOTH){
                        assert(new_v_node->left->left->node_version != ONETIME_VERSION);
                        assert(new_v_node->left->right->node_version != ONETIME_VERSION);
                    }
                    new_v_node->left->node_version = new_v_node->node_version;
                }
            }
            if(!intersect(l,r,resource_node->right->rangeLeft,resource_node->right->rangeRight)){
                if(new_v_node->right->node_version == new_v_node->node_version){
                    if(new_v_node->right->valid_check_child() == Node::BOTH){
                        assert(new_v_node->right->left->node_version != ONETIME_VERSION);
                        assert(new_v_node->right->right->node_version != ONETIME_VERSION);
                    }
                    delete new_v_node->right;
                }
                new_v_node->right = resource_node->right;
                if(new_v_node->right->node_version == ONETIME_VERSION){
                    if(new_v_node->right->valid_check_child() == Node::BOTH){
                        assert(new_v_node->right->left->node_version != ONETIME_VERSION);
                        assert(new_v_node->right->right->node_version != ONETIME_VERSION);
                    }
                    new_v_node->right->node_version = new_v_node->node_version;
                }
            }
        }
        reverse(RangeDFS_v1copy.begin(),RangeDFS_v1copy.end());
        for(Node* nd : RangeDFS_v1copy){
            assert(nd->node_version == this->version());
            if(nd->valid_check_child() == Node::NOCHILD)continue;
            nd->NodeUpdate();
        }
        this->FreeOneTimeVersion();
        memo_versionflow(v1,this->version());
        memo_versionflow(v2,this->version());
    }
    Node RangeMerge(index_int l , index_int r , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= l && l < r && r <= Rlimit());
        m_OneTime_root = new Node(*m_RootVersion[ver],ONETIME_VERSION);
        vector<Node*> bucket = RangeOneTimeSegments(l,r);
        assert(bucket.size() > 0);
        Node ProductNode(*bucket[0],ONETIME_VERSION);
        ProductNode.left = nullptr;
        ProductNode.right = nullptr;
        for(int i = 1 ; i < bucket.size() ; i++){
            ProductNode.Max = max(ProductNode.Max, bucket[i]->Max);
            ProductNode.Min = min(ProductNode.Min, bucket[i]->Min);
            ProductNode.Sum = ProductNode.Sum + bucket[i]->Sum;
            ProductNode.ProdSum = ProductNode.ProdSum + bucket[i]->ProdSum;
        }
        this->FreeOneTimeVersion();
        return ProductNode;
    }
    void RangeAffine(index_int l , index_int r, T A , T B, int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= l && l < r && r <= Rlimit());
        Node* nRoot = new Node(*m_RootVersion[ver] , m_RootVersion.size());
        vector<Node*> DfsRoute = RangeDFSRoute(l,r,nRoot);
        m_RootVersion.push_back(nRoot);
        reverse(DfsRoute.begin(),DfsRoute.end());
        for(Node* nd : DfsRoute){
            assert(nd->node_version == nRoot->node_version);
            if(CommonArea(l,r,nd->rangeLeft , nd->rangeRight) == nd->range_length())nd->set_lazyAffine(A,B);
            else nd->NodeUpdate();
        }
        this->FreeOneTimeVersion();
        memo_versionflow(ver,this->version());
    }
    void RangeAdd(index_int l , index_int r, T x, int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= l && l < r && r <= Rlimit());
        RangeAffine(l,r,T(1),x,ver);
    }
    void RangeUpdate(index_int l , index_int r, T x , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= l && l < r && r <= Rlimit());
        RangeAffine(l,r,T(0),x,ver);
    }
    T get(index_int i , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(Llimit() <= i && i < Rlimit());
        return RangeMerge(i,i+1,ver).Max;
    }
    template<typename type_merge>
    index_int binsearch_on_segtree(
            const index_int L , const index_int R ,
            type_merge Eq , function<T(type_merge , Node*)> op ,
            function<bool(type_merge)> judge , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        m_OneTime_root = new Node(*m_RootVersion[ver],ONETIME_VERSION);
        vector<Node*> bucket = RangeOneTimeSegments(L,R);
        vector<type_merge> prefixprod;
        type_merge prod = Eq;
        for(Node* tmp : bucket){
            prod = op(prod,tmp);
            prefixprod.push_back(prod);
        }
        while(bucket.size() != 0){
            prod = Eq;
            Node* tmp = bucket.back();
            assert(tmp->node_version == ONETIME_VERSION);
            tmp->eval(true,true);
            if(tmp->valid_check_child() == Node::BOTH){
                assert(tmp->left->node_version == ONETIME_VERSION);
                assert(tmp->right->node_version == ONETIME_VERSION);
            }
            prefixprod.pop_back();
            bucket.pop_back();
            if(prefixprod.size()>0)prod = prefixprod.back();
            if(judge(prod))continue;
            bucket.push_back(tmp);
            prod = op(prod,tmp);
            prefixprod.push_back(prod);
            if(bucket.back()->range_length() <= 1)break;
            prod = Eq;
            bucket.pop_back();
            prefixprod.pop_back();
            if(prefixprod.size()>0)prod = prefixprod.back();
            bucket.push_back(tmp->left);
            tmp->left->eval(false,false);
            prefixprod.push_back(op(prod,tmp->left));
            bucket.push_back(tmp->right);
            tmp->right->eval(false,false);
            prefixprod.push_back(op(op(prod,tmp->left),tmp->right));
        }
        assert(bucket.size() > 0);
        index_int res = bucket.back()->rangeRight;
        this->FreeOneTimeVersion();
        return res;
    }
    template<typename F>string format_num(F x , int digit_size = 4){
        ostringstream sout;
        sout.precision(digit_size+1);
        sout<<x;
        string res = sout.str();
        if(res.size() > digit_size){
            while(res.size() > digit_size)res.pop_back();
            res.back() = '~';
        }
        while(res.size() < digit_size)res.push_back(' ');
        return res;
    }
    template<int digit_size = 4>
    void DebugFlow(int l , int r){
        vector<pair<int,int>> update_info;
        for(int i = 0 ; i <= this->version();i++){
            for(int j : update_flow[i])update_info.emplace_back(i,j);
        }
        vector<vector<int>> debug_symbol(this->version()+1, vector<int>(update_info.size(),0));
        sort(update_info.begin(),update_info.end(),[&](pair<int,int> a , pair<int,int> b){
            if(update_flow[a.first].size() == update_flow[b.first].size()){
                if(a.first == b.first)return bool(a.second > b.second);
                return bool(a.first > b.first);
            }
            return bool(update_flow[a.first].size() < update_flow[b.first].size());
        });
        for(int flow_num = 0; flow_num < update_info.size() ; flow_num++){
            int ref = update_info[flow_num].first;
            int call = update_info[flow_num].second;
            for(int i = ref + 1 ; i < call ; i++)debug_symbol[i][flow_num] = 3;
            debug_symbol[ref][flow_num] = 1;
            debug_symbol[call][flow_num] = 2;
        }
        for(int i = 1 ; i < update_info.size() ; i++)cerr << "  ";
        cerr << "| update flow in range [" << l << " , " << r << ")" << endl;
        for(int i = 1 ; i < update_info.size() ; i++)cerr << "  ";
        cerr << "index  | ";
        for(int j = l ; j < r ; j++)cerr << format_num<T>(j,digit_size-1) << "| ";
        cerr << endl;
        for(int i = 0 ; i < debug_symbol.size() ; i++){
            for(int j = 0 ; j < debug_symbol[i].size() ; j++){
                if(debug_symbol[i][j] == 1)cerr << "F ";
                else if(debug_symbol[i][j] == 2)cerr << "L ";
                else if(debug_symbol[i][j] == 3)cerr << "| ";
                else cerr << "  ";
            }
            cerr << "ver " << format_num<int>(i,3) << ": ";
            for(int j = l ; j < r ; j++)cerr << format_num<T>(this->get(j,i),digit_size) << " ";
            cerr << endl;
        }
    }
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
};

template<typename type_key , typename type_size>
struct PersistentSegTreeSet{
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
    using Node = PersistentDynamicSegmentTree<type_key , type_size>::Node;
    inline static const int FIRST_VERSION = PersistentDynamicSegmentTree<type_key , type_size>::FIRST_VERSION;
    private:
    PersistentDynamicSegmentTree<type_key, type_size> S;
    type_size m_size = 0;
    type_key key_min,key_max;
    public:
    PersistentSegTreeSet(type_key key_min_ = -1000000001 ,type_key key_max_ = 1000000001)
        :key_min(key_min_), key_max(key_max_), S(key_min_,key_max_+1,0){}
    PersistentSegTreeSet(const PersistentSegTreeSet &x) = delete ;
    PersistentSegTreeSet& operator = (const PersistentSegTreeSet &x) = delete ;
    PersistentSegTreeSet ( PersistentSegTreeSet&& x){assert(0);}
    PersistentSegTreeSet& operator = ( PersistentSegTreeSet&& x){assert(0);}
    type_key max_limit(){return key_max;}
    type_key min_limit(){return key_min;}
    int version(){
        return this->S.version();
    }
    type_size size( int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        return S.RangeMerge(S.Llimit(),S.Rlimit(),ver).Sum;
    }
    void insert_together(vector<pair<type_key,type_size>> queries , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        for(int i = 0 ; i < queries.size() ; i++){
            assert(min_limit() <= queries[i].first && queries[i].first <= max_limit());
            assert(queries[i].second >= 0);
        }
        S.add_together(queries,ver);
    }
    void insert(type_key x , type_size c , int ver){
        assert(min_limit() <= x && x <= max_limit());
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(c>=0);
        S.add(x,c,ver);
    }
    void erase_together(vector<pair<type_key,type_size>> queries , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        for(int i = 0 ; i < queries.size() ; i++){
            assert(min_limit() <= queries[i].first && queries[i].first <= max_limit());
            assert(queries[i].second >= 0);
            queries[i].second *= -1;
        }
        S.add_together(queries,ver);
        for(int i = 0 ; i < queries.size() ; i++)assert(this->S.get(queries[i].first) >= 0);
    }
    void erase(type_key x , type_size c, int ver){
        assert(min_limit() <= x && x <= max_limit());
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(c>=0);
        assert(S.get(x,ver) >= c);
        S.add(x,-c,ver);
    }
    void set_together(vector<pair<type_key,type_size>> queries , int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(queries.size() > 0);
        for(int i = 0 ; i < queries.size() ; i++){
            assert(min_limit() <= queries[i].first && queries[i].first <= max_limit());
            assert(queries[i].second >= 0);
        }
        S.update_together(queries,ver);
    }
    type_size lower_bound(type_key x, int ver){
        assert(min_limit() <= x && x <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        if(x == key_min)return type_size(0);
        return S.RangeMerge(key_min,x,ver).Sum;
    }
    type_size upper_bound(type_key x, int ver){
        assert(min_limit() <= x && x <= max_limit());
        assert(FIRST_VERSION <= ver && ver <= this->version());
        return S.RangeMerge(key_min,x+1,ver).Sum;
    }
    type_size count(type_key x, int ver){
        assert(min_limit() <= x && x <= max_limit());
        assert(FIRST_VERSION <= ver && ver <= this->version());
        return S.get(x, ver);
    }
    type_size count(type_key k_l , type_key k_r, int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        return S.RangeMerge(k_l,k_r,ver).Sum;
    }
    type_size find(type_key x , int ver){
        assert(min_limit() <= x && x <= max_limit());
        if(this->count(x,ver) == 0)return -1;
        return this->lower_bound(x,ver);
    }
    type_size get_sum(type_key k_l , type_key k_r , int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        return S.RangeMerge(k_l,k_r,ver).ProdSum;
    }
    type_size range_sum(type_size l ,type_size r, int ver){
        assert(0 <= l && l < r && r <= size(ver));
        assert(FIRST_VERSION <= ver && ver <= this->version());
        type_size res = 0;
        type_key Lkey = this->get(l,ver);
        res += Lkey*(this->count(min_limit() , Lkey+1,ver) - l);
        if(this->size(ver)<=r){
            if(Lkey+1 <= key_max)res += this->get_sum(Lkey+1,key_max+1,ver);
            return res;
        }
        type_key Rkey = this->get(r ,ver);
        if(Lkey == Rkey)return (r-l)*Lkey;
        res += Rkey*(r - this->count(min_limit() , Rkey , ver));
        if(Lkey+1 < Rkey)res += this->get_sum(Lkey+1,Rkey,ver);
        return res;
    }
    void range_insert(type_key k_l , type_key k_r , type_size c, int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(c>=0);
        S.RangeAdd(k_l,k_r,c,ver);
    }
    void range_erase(type_key k_l , type_key k_r , type_size c, int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(S.RangeMerge(k_l,k_r,ver).Min >= c);
        S.RangeAdd(k_l,k_r,c*type_size(-1),ver);
    }
    void multiple_insert(type_key k_l , type_key k_r , type_size c, int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(c>=1);
        S.RangeAffine(k_l,k_r,c,type_size(0),ver);
    }
    void uniform_insert(type_key k_l , type_key k_r , type_size c, int ver){
        assert(min_limit() <= k_l && k_l < k_r && k_r <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(c>=0);
        S.RangeUpdate(k_l,k_r,c,ver);
    }
    type_key get(type_size ind , int ver){
        assert(0 <= ind && ind < size(ver));
        assert(FIRST_VERSION <= ver && ver <= this->version());
        type_size Eq = 0;
        function<type_size(type_size,Node*)> op = [&](type_size p , Node* nd){return p+nd->Sum;};
        type_size border_value = ind+1;
        function<bool(type_size)> judge = [&](type_size val){return bool(val >= border_value);};
        type_key border_ok = S.binsearch_on_segtree(min_limit(),max_limit()+1,Eq,op,judge,ver);
        assert(min_limit() < border_ok);
        assert(judge(S.RangeMerge(min_limit(),border_ok,ver).Sum));
        return border_ok - 1;
    }
    type_key minimum_freq(type_key L, type_key R , int ver){
        assert(min_limit() <= L && L < R && R <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(this->count(L,R,ver) > 0);
        type_size Eq = S.RangeMerge(L,R,ver).Max+1;
        function<type_size(type_size,Node*)> op = [&](type_size p , Node* nd){return min(p,nd->Min);};
        type_size border_value = S.RangeMerge(L,R,ver).Min;
        function<bool(type_size)> judge = [&](type_size val){return bool(val <= border_value);};
        type_key border_ok = S.binsearch_on_segtree(L,R,Eq,op,judge,ver);
        assert(L < border_ok);
        assert(judge(S.RangeMerge(L,border_ok,ver).Min));
        return border_ok - 1;
    }
    type_key maximum_freq(type_key L, type_key R, int ver){
        assert(min_limit() <= L && L < R && R <= max_limit()+1);
        assert(FIRST_VERSION <= ver && ver <= this->version());
        assert(this->count(L,R,ver) > 0);
        type_size Eq = S.RangeMerge(L,R,ver).Min-1;
        function<type_size(type_size,Node*)> op = [&](type_size p , Node* nd){return max(p,nd->Max);};
        type_size border_value = S.RangeMerge(L,R,ver).Max;
        function<bool(type_size)> judge = [&](type_size val){return bool(val >= border_value);};
        type_key border_ok = S.binsearch_on_segtree(L,R,Eq,op,judge,ver);
        assert(L < border_ok);
        assert(judge(S.RangeMerge(L,border_ok,ver).Max));
        return border_ok - 1;
    }
    void Debug(int ver){
        assert(FIRST_VERSION <= ver && ver <= this->version());
        cerr << "version "<< ver << " : " << this->size(ver) << " element(s)."<< endl;
        unordered_map<type_key,int> viewed;
        for(type_size i = 0 ; i < this->size(ver) ; i++){
            if(viewed[this->get(i , ver)]++)continue;
            cerr << i << " th element = " << this->get(i , ver) << " x " << this->count(this->get(i,ver), ver) << endl;
        }
    }
    void DebugFlow(type_key l , type_key r){
        cerr << "| debug with counts of elements and " << endl;
        S.DebugFlow(l,r);
    }
    void test_rangecp(type_key l , type_key r , int v1 ,int v2 ){S.RangeCopy(l,r,v1,v2);}
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
};

void test_persistent_datastructure(){
    using ll = long long;
    using pll = pair<ll,ll>;
    using vpll = vector<pll>;
    using namespace std;
    ll Llim = -500;
    ll Rlim = 500;
    PersistentSegTreeSet<ll,ll> S(Llim , Rlim);
    PersistentSegTreeSet<ll,ll> LazyS(Llim , Rlim);
    int testcnt = 400000;
    vector<string> qtype(12,"undefined");
    qtype[0] = "insert_together(rand)";
    qtype[1] = "erase(x,c)";
    qtype[2] = "get(i)";
    qtype[3] = "count(x)";
    qtype[4] = "count(l,r)";
    qtype[5] = "get_sum(l,r)";
    qtype[6] = "range_sum(li,ri)";
    qtype[7] = "maximum_freq(l,r)";
    qtype[8] = "minimum_freq(l,r)";
    qtype[9] = "uniform_insert(l,r)";
    qtype[10] = "range_insert(l,r)";
    qtype[11] = "RangeCopy(l,r)";
    while(testcnt-->0){
        int t = rand()%12;
        ll x = Llim + rand()%(Rlim-Llim+1);
        int c = rand()%30+1;
        int v = rand()%(S.version()+1);
        ll l = Llim + rand()%(Rlim-Llim+1);
        ll r = Llim + rand()%(Rlim-Llim+1);
        if(l>r)swap(l,r);
        r++;
        ll li = rand()%S.size(v);
        ll ri = rand()%S.size(v);
        if(li>ri)swap(li,ri);
        ri++;
        if(t == 0){
            vector<pll> qrs;
            for(int i = 0 ; i < c ; i++)qrs.emplace_back(Llim + rand()%(Rlim-Llim+1),rand()%10+1);
            S.insert_together(qrs,v);
            LazyS.insert_together(qrs,v);
        }else if(t == 1){
            if(S.count(x,v) < c)c = S.count(x,v);
            S.erase(x,c,v);
            LazyS.erase(x,c,v);
        }else if(t == 2){
            if(S.size(v) > 0){
                int i = rand()%S.size(v);
                if(LazyS.get(i,v) != S.get(i,v)){
                    assert(LazyS.get(i,v) == S.get(i,v));
                }
            }
        }else if(t == 3){
            assert(LazyS.count(x,v) == S.count(x,v));
        }else if(t == 4){
            if(LazyS.count(l,r,v) != S.count(l,r,v)){
                assert(LazyS.count(l,r,v) == S.count(l,r,v));
            }
        }else if(t == 5){
            if(LazyS.get_sum(l,r,v) != S.get_sum(l,r,v)){
                assert(LazyS.get_sum(l,r,v) == S.get_sum(l,r,v));
            }
        }else if(t == 6){
            if(S.size(v) > 0 && 0){
                if(LazyS.range_sum(li,ri,v) != S.range_sum(li,ri,v)){
                    assert(LazyS.range_sum(li,ri,v) == S.range_sum(li,ri,v));
                }
            }
        }else if(t == 7){
            if(LazyS.count(l,r,v) != S.count(l,r,v)){
                assert(LazyS.count(l,r,v) == S.count(l,r,v));
            }
            if(S.count(l,r,v) > 0)assert(LazyS.maximum_freq(l,r,v) == S.maximum_freq(l,r,v));
        }else if(t == 8){
            assert(S.count(l,r,v) == LazyS.count(l,r,v));
            if(S.count(l,r,v) > 0)assert(LazyS.minimum_freq(l,r,v) == S.minimum_freq(l,r,v));
        }else if(t == 9){
            vpll qrs;
            int u = rand()%10000 + 1;
            for(int i = l ; i < r ; i++)qrs.emplace_back(i,u);
            S.set_together(qrs,v);
            LazyS.uniform_insert(l,r,u,v);
        }else if(t == 10 ){
            vpll qrs;
            int u = rand()%10000 + 1;
            for(int i = l ; i < r ; i++)qrs.emplace_back(i,u);
            S.insert_together(qrs,v);
            LazyS.range_insert(l,r,u,v);
        }else if(t == 11){
            int v2 = rand()%(S.version()+1);
            vpll qrs;
            for(int i = l ; i < r ; i++)qrs.emplace_back(i,S.count(i,v));
            S.set_together(qrs,v2);
            LazyS.test_rangecp(l,r,v,v2);
            assert(S.version() == LazyS.version());
        }
        if(testcnt%100 == 0){
            vpll qrs;
            for(int i = Llim ; i <= Rlim ; i++)qrs.emplace_back(i,0);
            S.set_together(qrs,v);
            LazyS.uniform_insert(Llim,Rlim+1,0,v);
        }
        if(testcnt%10000 == 0){
            cerr << "OK : rem = " << testcnt << endl;
        }
    }
};

int main(){
    test_persistent_datastructure();
}

使用例

TODOにしておきます。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

通常/双対/遅延評価/動的/二分探索/多次元/全永続 セグメント木 (セグ木,セグメントツリー) (コード例付き)