まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
はじめに
覆水盆に返る。データの更新を行えるデータ構造に対して、更新前のデータを旧バージョン、更新後のデータを新バージョンと呼ぶことにします。永続データ構造では、更新を行った後からでも過去のデータにアクセスすることができます。また、今回扱うデータ構造のように過去のデータから新バージョンを作ることができるデータ構造を全永続(完全永続)データ構造と言います。
目次
この記事では全永続化した多重集合の作り方を紹介します。以下は内容です。
-
セグメント木
- 列の区間に対する集約の取得
- 値の更新
-
動的セグメント木
- 初期状態
- 頂点の動的確保
- セグメント木上の二分探索
-
セグメント木の全永続化
- 根のバージョン管理
- メモリに配慮した戦略
-
全永続多重集合
- 基本機能
- ランダムアクセス
- 最頻値
- 個数が最も少ない要素
- 総和の計算
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 動的セグメント木
通常のセグメント木では初期状態の数列が与えられていたため、セグメント木全体でカバーする範囲が $[0,数列サイズ)$ 程度でした。
動的セグメント木では、初期状態として区間 $[\mathrm{Lmost},\mathrm{Rmost})$ と初期値 $\mathrm{iv}$ が与えられます。この時、動的セグメント木は、定義域が $[\mathrm{Lmost},\mathrm{Rmost})$ であり、$\mathrm{iv}$ で初期化された列を表現します。動的セグメント木の利点として、定義域 $[\mathrm{Lmost},\mathrm{Rmost})$ が巨大な場合や、負の領域である場合にも対処できることがあります。
動的セグメント木では、各セグメントは数列の要素を表現する値 $\mathrm{V}$ と集約 (今回は $\mathrm{Sum}$) を持ちます。ただし、通常のセグメント木と同様に、数列の要素を表現する $\mathrm{V}$ は末端セグメントのみ有効なものとして問題ありません。ただし、動的セグメント木における末端セグメントとは、左右の子の少なくとも一方が存在しないセグメントを指します。
1.3.1 初期状態
$[\mathrm{Lmost},\mathrm{Rmost})$ をカバーするセグメント木のセグメントを全て構築してしまうと、$O(\mathrm{Rmost}-\mathrm{Lmost})$ 個のセグメントが必要になってしまいます。そこで、動的セグメント木の初期状態では区間 $[\mathrm{Lmost},\mathrm{Rmost})$ をカバーする根のみを管理します。
例えば以下の図は、区間 $[0,9)$ を $\mathrm{iv} = 3$ で初期化した動的セグメント木です。根以外のノードはまだ生成されていません。セグメントの左右の子がまだ生成されていない場合、それらの集約から自身の集約を計算できないので、集約 $\mathrm{Sum}$ を自身がカバーする範囲と自身が持つ値 $\mathrm{V}$ から計算する必要があります。
この動的セグメント木は数列 $\{3,3,3,3,3,3,3,3,3\}$ を表現しています。この数列の index は $0$ 以上 $9$ 未満の整数ですが、区間 $[\mathrm{Lmost},\mathrm{Rmost})$ が負の領域に至る場合などのように、数列の index として負の整数をとることも可能です。
補足
セグメント木の末端セグメントのサイズを $\varepsilon$ とすると、精度が $\varepsilon$ 程度の実数を index にすることもできます。ただしこの場合、集約 $\mathrm{Sum}$ の計算に注意が必要です (積分をイメージするとよい)。
1.3.2 頂点の動的確保
動的セグメント木も通常のセグメント木のように、セグメントをうまく選択することでデータの取得を行います。動的セグメント木ははじめから全てのセグメントを明示的に用意しているわけではないので、必要なセグメント及びそのセグメントにアクセスするパスを動的に確保する必要があります。
例として、区間 $[2,4)$ のデータを取得する場合を示します。以下の図は、区間 $[2,4)$ にアクセスするために根の左右の子を確保する様子です。このとき、根が持つ値 $\mathrm{V}$ を左右の子に継承します。また、根が末端でなくなったので今後は根に対して $\mathrm{V}$ を考える必要が無くなりました。
根は区間 $[0,9)$ に対応しているので、これを半分程度に分割して左右の子セグメントとします。新たに確保した左右の子は、自身が持つ集約 $\mathrm{Sum}$ を自身が持つ情報から計算する必要があります。
左右の子セグメントが対応する区間 $[0,4)$ と$[4,9)$ のうち、目的の区間 $[2,4)$ は左の子セグメントの区間 $[0,4)$ に含まれるので、左の子に降りて探索を再開します。先ほどと同様に左右の子を動的確保して探索をすることで、以下のように目的の区間 $[2,4)$ を確保することができます。
セグメント木上の二分探索
区間の片方の端を固定したとき、他方の端としてあり得る領域を「条件を満たさない領域」と「条件を満たす領域」に二分することを考えます。例えば、以下は区間の左端 $L$ を固定したときに、区間内要素の総和が $9$ 以上であるかどうかで右端 $R$ の領域を分割した様子です。
このような領域の分割を、以下のパラメータを用いて抽象化することができます。ただし、このパラメータは区間の左端を固定する場合のものです。
- $L := $ 区間の左端の index
- $Rlim := $ $R$ として許容する上限値
- $Eq := $ 区間内の要素を集約するモノイドの単位元
- $op(a,b) := $ 区間内の要素を集約するモノイドの二項演算
- $judge(x) :=$ $op$ による区間の集約値 $x$ が、条件を満たすかどうかを bool で返す関数
このようなパラメータに対して、領域の境界をセグ木 $S$ 上で愚直に二分探索してしまうと、二分探索のイテレーション $O(\log{(数列サイズ)})$ 回それぞれの区間取得に $O(\log{(数列サイズ)})$ 時間かかってしまい、$\log$ に二乗がついてしまいます。
そこで、セグメント木のセグメントがうまく分割統治を行っていることを利用します。二分探索のイテレーションでアクセスする地点をセグメントの端点に一致させることで、区間の集約の取得にかかる $\log$ を一つ落とすことができます。
まず、固定する左端 $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}$ とその累積集約に反映させます。以降も同様に探索すべき領域の特定を進めていきます。
また、この処理でも必要があれば子セグメントの動的確保を行う必要があります。
処理の結果、探索するべき領域が末端セグメントになれば探索は終了です。このとき、$\mathrm{bucket}$ の中身のセグメントは条件を満たすギリギリの区間 $[L,R)$ に対応します。
3 動的セグメント木の全永続化
動的セグメント木の初期状態を Ver.0、表現する列を $S^{(0)}$ として、動的セグメント木を全永続化します。
冒頭で説明した通り、永続データ構造では更新によるデータの変更を新バージョンの生成と捉えます。また、データ更新前のデータ (過去のバージョン) に自由にアクセスすることができます。
新バージョンをコピーで愚直に生成するのは当然計算量的にありえないので、新バージョン生成の見方を変えて、データ自体のコピーを行うのではなく、データにアクセスするインターフェースのコピーを行うことにします。セグメント木の構造においては、インターフェースが省メモリであるという点で永続化との相性が良いのです。
3.1 根のバージョン管理
セグメント木の根は全体へのアクセスをもつインターフェースなので、根をコピーすることでバージョンの複製をすることにします。ただし全く同じものを作っても意味がないので、根以外にもデータの変更による影響があるセグメント及び、それらへのアクセスに必要なセグメントをコピーします。
以下の図は、変更したデータへのアクセスに関する部分だけをインターフェースとしてコピーすることで、Ver.0 から Ver.1 を生成した様子です。旧バージョンの根から更新したい要素までの経路を取得し、それをコピーして新バージョンとしています。ただし、セグメントをコピーする前にそのセグメントの子の動的確保を完了させておいてください。
なお、新たなバージョンの生成によって参照関係が増えるので、全永続動的セグメント木のセグメントには親セグメントへのポインタを持たせません。よって通常のセグメント木のようにデータ更新後に親へのポインタを辿って上側のセグメントの集約を計算することはできません。複製した経路を一時的に管理して集約を計算する必要があります。
新バージョンのデータも変更があった場所以外は過去のバージョンと同じです。新バージョンで新た生成されたセグメント間には新たな参照関係をつくり、それ以外は過去のバージョンのセグメントを参照することで、過去のデータの無駄な複製を回避できるのです。例えば以下の図は Ver.1 のデータ $S^{(1)}[0]$ にアクセスする様子ですが、実際は Ver.1 のインターフェースから参照を辿って $S^{(0)}[0]$ と同じデータにアクセスしていることが確認できます。
また、以下は Ver.1 から新たに Ver.2 を作成する様子です。Ver.1 の根から更新を行う要素までの経路を構築し、それをコピーして Ver.2 のインターフェースとします。以下の例のようにセグメントの参照がバージョンをまたぐ場合、さらに過去のバージョンのセグメントがコピーされます。
また、セグメントをコピーする前にそのセグメントの子の動的確保を完了させているので、セグメントの動的確保が実行されるのは常に Ver.0 のセグメント木です。上図もこのことに従っていることが確認できます。
最後に、過去のバージョンに変更を加えて最新バージョンを作成する例を説明します。経路の探索を始める根のバージョンを指定することで、変更を加えるバージョンを指定することができます。以下の図は Ver.1 における経路をコピーして Ver.3 を得る様子です。
Ver.1 から Ver.2 と Ver.3 に分岐してしまいましたが、Ver.1 を参照するインターフェースが増えただけで Ver.2 に影響がないことも確認できます。
3.2 メモリに配慮した戦略
動的セグメント木を全永続化する都合上、初期状態の列 $S^{(0)}$ は全体が初期値で初期化された状態から始まります。ここでは、表現したい列のデータが以下の形式のデータの集まり $Q$ としてあらかじめ与えられている場合を考えます。
- $\{ i , x \} := $ index が $i$ の要素は $x$ である。
一回の更新で約 $\log{(数列サイズ)}$ 個のセグメントがコピーされてしまうので、これら $|Q|$ 個のデータを一つずつ反映していくと、全体で生成されるコピーが大きくなってしまいます。
これはメモリの無駄遣いなので、一つ更新するごとにコピーを生成するのをやめます。全ての更新を行なった後、その影響があった部分を全て一度にコピーすることで、コピーのサイズを減らすことができます。この戦略の効果は更新を行う index の分布に影響を受けますが、一般には $|Q|$ が大きいほど有効と考えて良いでしょう。
$\{ i , x \}$ の情報を $i$ の昇順にソートし、$i$ が小さい順に対応するセグメントを訪れる DFS を行うことで、影響がある部分を重複なく取得できます。またこの道中で集約の計算などを行います。
全永続多重集合
全永続セグメント木上でも通常のセグメント木上と同様に二分探索を行うことができます。このことを用いて、ランダムアクセスや格納された要素の集約の取得が可能な全永続多重集合を作ります。
整数の集合をプログラムで管理する際、最もシンプルな方法は以下のような配列 $S$ を管理しておくことです。
- $S[x]$ := 集合に含まれる整数 $x$ の個数
この配列 $S$ を全永続動的セグメント木で管理します。なお、管理する整数が小さい場合や、あらかじめ座標圧縮できる場合は動的でない通常のセグ木で十分です。
4.1 基本機能
全永続動的セグメント木を用いることで、多重集合の基本的な機能を以下で定義できます。
- $\mathrm{insert}(x,c,v) := v$ で指定したバージョンに $x$ を $c$ 個追加し、それを新バージョンとする。$S^{(v)}[x]$ に $c$ 加算すれば良い。
- $\mathrm{erase}(x,c,v) := v$ で指定したバージョンから $x$ を $c$ 個削除し、それを新バージョンとする。$S^{(v)}[x]$ に $-c$ 加算すれば良い。
- $\mathrm{lower\_bound}(x,v) := v$ で指定したバージョンに格納されている要素のうち、$x$ 未満の要素数。$S^{(v)}[x-1]$ までの prefix_sum (区間和で取得) のこと
- $\mathrm{upper\_bound}(x,v) := v$ で指定したバージョンに格納されている要素のうち、$x$ 以下の要素数。$S^{(v)}[x]$ までの prefix_sum (区間和で取得) のこと
- $\mathrm{count}(x,v) := v$ で指定したバージョンに格納されている $x$ の個数。$S^{(v)}[x]$ のこと
- $\mathrm{count}(l,r,v) := v$ で指定したバージョンに格納されている要素のうち、$l$ 以上 $r$ 未満の要素数。$S^{(v)}$ の $[l,r) $ の区間和のこと
4.2 ランダムアクセス
全永続動的セグメント木上の二分探索を用いることで、要素へのランダムアクセスを定義できます。
- $\mathrm{get(i,v)} := v$ で指定したバージョンに格納されている要素のうち、昇順で $i$ 番目の要素を取得する。
左端が $\mathrm{Lmost}$ で固定されており、右端の上限が $\mathrm{Rmost}$ である区間で、区間内要素の総和が $i+1$ 以上となる区間の右端の境界 $R$ を二分探索で求めると、$R-1$ が答えになります。( $2$ 章で動的セグメント木の index の範囲を $[\mathrm{Lmost},\mathrm{Rmost})$ と定義しました。)
4.3 最頻値
多重集合に含まれる要素のうち、最も多く含まれるものを計算できます。
- $\mathrm{maximum\_freq}(l,r,v) := v$ で指定したバージョンに格納されている要素のうち、$l$ 以上 $r$ 未満の要素の要素で、集合に最も多く登場する要素
$Eq := -\infty$ , $op := max$ とし、定数 $bdr$ を「$l$ 以上 $r$ 未満の要素で、最も多い登場回数」とします。$bdr$ は区間最大値をセグメント木から取得することで求まります。ここで、条件 $judge(x)$ を「$\mathrm{bucket}$ 内の最大値 $x$ が $bdr$ 以上である」と定義して二分探索すると、区間の右端 $R$ に対して $R-1$ が答えになります。
ただし複数存在する場合は、そのうち最小のものを返します。また区間の右端を固定して二分探索をすると、最も大きいものを返します。
4.4 個数が最も少ない要素
最頻値の反対もできます。
- $\mathrm{minimum\_freq}(l,r,v) := v$ で指定したバージョンに格納されている要素のうち、$l$ 以上 $r$ 未満の要素の要素で、集合に格納されている個数が最も少ない要素。ただし、$0$ 個のものも含む。
最頻値と同じような二分探索も可能ですが、セグメント木 $S^{(v)}$ に記録した値の符号を反転することで、最頻値と同じ二分探索に帰着できます。また、$0$ 個のものを含まないようにするためには、$S^{(v)}$ に $0$ の代わりに $-\infty$ を格納すると良いです。ただし、$\mathrm{insert} , \mathrm{erase}$ の際に処理を場合分けする必要があることに注意してください。
4.5 総和の計算
セグメント木の集約として $\mathrm{ProdSum} := \sum{i\times S[i]}$ を定義します。これを用いることで、指定した範囲内の要素の総和を取得できます。
- $\mathrm{get\_sum}(l,r,v) := v$ で指定したバージョンにおける $l$ 以上 $r$ 未満の要素の総和
- $\mathrm{range\_sum}(l,r,v) := v$ で指定したバージョンに格納されている要素を昇順で並べたとき、区間 $[l,r)$ に含まれる要素の総和
ソースコード
ライセンスは守ってくださいね (このライブラリの冒頭に以下を書くだけで良いです)。
- Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024. Released under the MIT license(https://opensource.org/licenses/mit-license.php)
ライセンスに従わない利用を確認した場合、ライセンスに従わない利用をやめるよう指示するなどの処置を取る場合があります。
#include<iostream>
#include<cassert>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<ostream>
#include<sstream>
#include<functional>
#include<map>
using namespace std;
/*
このコメントは消さないでください。
Don't Remove this Comment !!
Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
Released under the MIT license(https://opensource.org/licenses/mit-license.php)
*/
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 int LATEST_VERSION_SYMBOL = -1;
inline static const int FIRST_VERSION = 0;
struct Node{
void make_child(){
if(this->left == nullptr && this->right == nullptr && this->range_length() > 1){
this->left = new Node(this->range.first,((this->range.first+this->range.second)>>1),this->Value);
this->right = new Node(((this->range.first+this->range.second)>>1),this->range.second,this->Value);
}
}
pair<index_int,index_int> range;
Node* left = nullptr;
Node* right = nullptr;
T Value ;
T Sum ,Max, Min;
T ProdSum;
Node(){}
Node(const Node& p) = default;
Node(index_int l , index_int r , T x){
this->range = {l,r};
Value = x;
Min = x;
Max = x;
Sum = range_length()*x;
ProdSum = (x*((range.second-1)*range.second-(range.first-1)*range.first))>>1;
}
constexpr index_int range_length()const{return (range.second - range.first);}
constexpr bool cover(index_int i)const{return bool(range.first <= i && i < range.second);}
void NodeUpdate(){
this->make_child();
if(range_length() <= 1){
Sum = Min = Max = Value;
ProdSum = Value*range.first;
return;
}
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;
}
};
private:
index_int _Llim,_Rlim;
const T init_value;
vector<Node*> m_RootVersion;
vector<vector<int>> update_flow = {{}};
Node* access(index_int i , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
Node* now = m_RootVersion[ver];
while(now->range_length() > 1){
now->make_child();
if(now->left->cover(i))now = now->left;
else now = now->right;
}
return now;
}
void RangeSegments(index_int l , index_int r , vector<Node*>& bucket , Node* subr){
subr->make_child();
if(r <= subr->range.first)return;
else if(l >= subr->range.second)return;
else if( l <= subr->range.first && subr->range.second <= r)bucket.push_back(subr);
else {
RangeSegments(l,r,bucket,subr->left);
RangeSegments(l,r,bucket,subr->right);
}
}
static void operate_update(T& a, T b){a = b;}
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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(queries.size() > 0);
m_RootVersion[ver]->make_child();
m_RootVersion.push_back(new Node(*m_RootVersion[ver]));
sort(queries.begin(),queries.end(),[&](pair<index_int,T> a , pair<index_int,T> b){return bool(a.first < b.first);});
Node* now = m_RootVersion.back();
vector<Node*> path;
path.push_back(now);
for(pair<index_int,T> q : queries){
assert(Llimit() <= q.first && q.first < Rlimit());
while(now->cover(q.first) == false){
path.back()->NodeUpdate();
path.pop_back();
now = path.back();
}
while(now->range_length() > 1){
if(now->left->cover(q.first)){
now->left->make_child();
path.push_back(new Node(*(now->left)));
now->left = path.back();
}else{
now->right->make_child();
path.push_back(new Node(*(now->right)));
now->right = path.back();
}
now = path.back();
}
upd(path.back()->Value,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)){}
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)){}
~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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= i && i < Rlimit());
update_together({{i,x}},ver);
}
void add_together(vector<pair<index_int,T>> queries , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(queries.size() > 0);
version_update<operate_add>(queries,ver);
}
void add(index_int i , T x , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= i && i < Rlimit());
add_together({{i,x}},ver);
}
T get(index_int i , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= i && i < Rlimit());
return access(i,ver)->Value;
}
T RangeMinQuery(index_int l , index_int r , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= l && l < r && r <= Rlimit());
vector<Node*> bucket;
RangeSegments(l,r,bucket,m_RootVersion[ver]);
assert(bucket.size() > 0);
T res = bucket[0]->Min;
for(int i = 1 ; i < bucket.size() ; i++)res = min(res,bucket[i]->Min);
return res;
}
T RangeMaxQuery(index_int l , index_int r , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= l && l < r && r <= Rlimit());
vector<Node*> bucket;
RangeSegments(l,r,bucket,m_RootVersion[ver]);
assert(bucket.size() > 0);
T res = bucket[0]->Max;
for(int i = 1 ; i < bucket.size() ; i++)res = max(res,bucket[i]->Max);
return res;
}
T RangeSumQuery(index_int l , index_int r , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= l && l < r && r <= Rlimit());
vector<Node*> bucket;
RangeSegments(l,r,bucket,m_RootVersion[ver]);
assert(bucket.size() > 0);
T res = bucket[0]->Sum;
for(int i = 1 ; i < bucket.size() ; i++)res += bucket[i]->Sum;
return res;
}
T RangeProdSumQuery(index_int l , index_int r , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(Llimit() <= l && l < r && r <= Rlimit());
vector<Node*> bucket;
RangeSegments(l,r,bucket,m_RootVersion[ver]);
assert(bucket.size() > 0);
T res = bucket[0]->ProdSum;
for(int i = 1 ; i < bucket.size() ; i++)res += bucket[i]->ProdSum;
return res;
}
template<typename type_merge>
vector<Node*> 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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
vector<Node*> bucket;
vector<type_merge> prefixprod;
RangeSegments(L,R,bucket,m_RootVersion[ver]);
type_merge prod = Eq;
for(int i = 0 ; i < bucket.size() ; i++){
bucket[i]->make_child();
prod = op(prod,bucket[i]);
prefixprod.push_back(prod);
}
while(bucket.size() != 0){
prod = Eq;
Node* tmp = bucket.back();
tmp->make_child();
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;
Node* lef = bucket.back()->left;
Node* rig = bucket.back()->right;
prod = Eq;
bucket.pop_back();
prefixprod.pop_back();
if(prefixprod.size()>0)prod = prefixprod.back();
bucket.push_back(lef);
lef->make_child();
prefixprod.push_back(op(prod,lef));
bucket.push_back(rig);
rig->make_child();
prefixprod.push_back(op(op(prod,lef),rig));
}
return bucket;
}
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<vector<int>> debug_symbol(this->version()+1, vector<int>(this->version(),0));
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);
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 < debug_symbol.size() ; i++)cerr << " ";
cerr << "| update flow in range [" << l << " , " << r << ")" << endl;
for(int i = 1 ; i < debug_symbol.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)
*/
};
/*
このコメントは消さないでください。
Don't Remove this Comment !!
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 LATEST_VERSION_SYMBOL = PersistentDynamicSegmentTree<type_key , type_size>::LATEST_VERSION_SYMBOL;
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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
return this->count(key_min,key_max+1,ver);
}
void insert_together(vector<pair<type_key,type_size>> queries , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(queries.size() > 0);
for(int i = 0 ; i < queries.size() ; i++)assert(queries[i].second >= 0);
S.add_together(queries,ver);
}
void insert(type_key x , type_size c , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(c>=0);
S.add(x,c,ver);
}
void erase_together(vector<pair<type_key,type_size>> queries , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(queries.size() > 0);
for(int i = 0 ; i < queries.size() ; i++){
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 = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
assert(c>=0);
assert(S.get(x,ver) >= c);
S.add(x,-c,ver);
}
type_size lower_bound(type_key x, int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
if(x == key_min)return type_size(0);
return S.RangeSumQuery(key_min,x,ver);
}
type_size upper_bound(type_key x, int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
return S.RangeSumQuery(key_min,x+1,ver);
}
type_size count(type_key x, int ver){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
return S.get(x, ver);
}
type_size count(type_key k_l , type_key k_r, int ver){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
return S.RangeSumQuery(k_l,k_r,ver);
}
type_size get_sum(type_key k_l , type_key k_r , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
return S.RangeProdSumQuery(k_l,k_r,ver);
}
type_size range_sum(type_size l ,type_size r, int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
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;
}
type_key get(type_size ind , int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
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);};
vector<Node*> segments = S.binsearch_on_segtree(min_limit(),max_limit()+1,Eq,op,judge,ver);
assert(segments.size() > 0);
type_size prod = Eq;
for(Node* nd : segments){
nd->make_child();
prod = op(prod,nd);
}
assert(judge(prod));
return segments.back()->range.first;
}
type_key maximum_freq(type_size L, type_size R, int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
type_size Eq = S.RangeMinQuery(L,R,ver)-1;
function<type_size(type_size,Node*)> op = [&](type_size p , Node* nd){return max(p,nd->Max);};
type_size border_value = S.RangeMaxQuery(L,R,ver);
function<bool(type_size)> judge = [&](type_size val){return bool(val >= border_value);};
vector<Node*> segments = S.binsearch_on_segtree(L,R,Eq,op,judge,ver);
assert(segments.size() > 0);
type_size prod = Eq;
for(Node* nd : segments){
nd->make_child();
prod = op(prod,nd);
}
assert(judge(prod));
return segments.back()->range.first;
}
void Debug( int ver = LATEST_VERSION_SYMBOL){
if(ver == LATEST_VERSION_SYMBOL)ver = this->version();
assert(FIRST_VERSION<=ver);
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);
}
/*
Copyright ©️ (c) NokonoKotlin (okoteiyu) 2025.
Released under the MIT license(https://opensource.org/licenses/mit-license.php)
*/
};
// verify 用
void test_persistent_datastructure(){
using ll = long long;
using pll = pair<ll,ll>;
using namespace std;
ll Llim = -1000;
ll Rlim = 1000;
PersistentSegTreeSet<ll,ll> S(Llim , Rlim);
vector<map<ll,ll>> T(1);
int testcnt = 80000;
while(testcnt-->0){
int t = rand()%7;
/*
t = 0 : insert(x,c,v);
t = 1 : erase(x,c,v);
t = 2 : get(i,v);
t = 3 : count(x,v);
t = 4 : count(l,r,v);
t = 5 : get_sum(l,r,v);
t = 6 : maximum_freq(l,r,v);
*/
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){
S.insert(x,c,v);
T.push_back(T[v]);
T.back()[x] += c;
}else if(t == 1 && S.count(x,v) > 0){
if(S.count(x,v) < c)c = S.count(x,v);
S.erase(x,c,v);
T.push_back(T[v]);
T.back()[x] -= c;
}else if(t == 2 && S.size(v) > 0){
int i = rand()%S.size(v);
ll Tvi;
ll ind = i;
for(pll p : T[v]){
if(ind >= p.second)ind-=p.second;
else{
Tvi = p.first;
break;
}
}
assert(Tvi == S.get(i,v));
}else if(t == 3){
assert(T[v][x] == S.count(x,v));
}else if(t == 4){
ll cntTv = 0;
for(pll p : T[v])if(l <= p.first && p.first < r)cntTv+=p.second;
assert(cntTv == S.count(l,r,v));
}else if(t == 5){
ll sumTv = 0;
for(pll p : T[v])if(l <= p.first && p.first < r)sumTv+=p.second*p.first;
assert(sumTv == S.get_sum(l,r,v));
}else if(t == 6){
ll mxf = -1;
ll mxf_val = -1;
for(ll i = l ; i < r ; i++){
if(T[v][i] > mxf){
mxf = T[v][i];
mxf_val = i;
}
}
assert(mxf_val == S.maximum_freq(l,r,v));
}
if(testcnt%10000 == 0)cerr << "OK : rem = " << testcnt << endl;
}
}
使用例
verify 問題がわからなかったので、test_persistent_datastructure() でテストをしました。
また、以下のような雰囲気で使います。
int main(){
PersistentSegTreeSet<int,int> S(-7,7);
S.insert(1,1);
S.insert(3,2);
S.insert(4,1);
S.insert(7,3);
S.Debug(S.version());
S.erase(3,2,3);// Ver.3 から 3 を 2 つ削除
S.Debug(S.version());//
vector<pair<int,int>> Q = {{-5,3},{-2,2},{0,3}};
S.insert_together(Q,2);// Ver.2 に Q を適用
S.Debug(S.version());
Q = {{1,1},{7,1}};
S.erase_together(Q,4);// Ver.4 に Q を適用
S.Debug(S.version());
Q = {{1,5},{2,4}};
S.insert_together(Q,6);
S.DebugFlow(S.min_limit(),S.max_limit()+1);
cerr << "check count(2,6,4) : " << S.count(2,6,4) << endl;
cerr << "check get(3,8) : " << S.get(3,8) << endl;
cerr << "check range_sum(2,5,6) : " << S.range_sum(2,5,6) << endl;
cerr << "check maximum_freq(-7,8,4) : " << S.maximum_freq(-7,8,4) << endl;
}
以下は出力です。
version 4 : 7 element(s).
0 th element = 1 x 1
1 th element = 3 x 2
3 th element = 4 x 1
4 th element = 7 x 3
version 5 : 2 element(s).
0 th element = 1 x 1
1 th element = 4 x 1
version 6 : 11 element(s).
0 th element = -5 x 3
3 th element = -2 x 2
5 th element = 0 x 3
8 th element = 1 x 1
9 th element = 3 x 2
version 7 : 5 element(s).
0 th element = 3 x 2
2 th element = 4 x 1
3 th element = 7 x 2
| debug with counts of elements and
| update flow in range [-7 , 8)
index | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
F ver 0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
F L ver 1 : 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
L F F ver 2 : 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0
F F | L ver 3 : 0 0 0 0 0 0 0 0 1 0 2 1 0 0 0
F | L | ver 4 : 0 0 0 0 0 0 0 0 1 0 2 1 0 0 3
| L | ver 5 : 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0
F | L ver 6 : 0 0 3 0 0 2 0 3 1 0 2 0 0 0 0
| L ver 7 : 0 0 0 0 0 0 0 0 0 0 2 1 0 0 2
L ver 8 : 0 0 3 0 0 2 0 3 6 4 2 0 0 0 0
check count(2,6,4) : 3
check get(3,8) : -2
check range_sum(2,5,6) : -9
check maximum_freq(-7,8,4) : 7