可持久化數據結構
可持久化數據結構
首先需要知道，何謂可持久化？具體而言，就是對每次操作保留一個歷史版本，同時可以基于其中一個歷史版本進行操作，且復雜度在可接受范圍內。
顯然不能每次都拷貝一遍，但是利用一些性質，一些常見的數據結構都是在同樣的復雜度下做到可持久化的。
可持久化線段樹（主席樹）
其實主席樹不完全等于可持久化線段樹，而是可持久化權值線段樹。不過現在似乎不太區分這個，索性都這么叫了。
基本思想
不能每次都開一棵線段樹，考慮到線段樹每次修改的一個重要性質：每次修改只會修改 \(\boldsymbol{O(\log n)}\) 個節點。
（圖源 OI Wiki）
所以簡單地，采用動態開點的方式儲存兒子，每次修改的時候把需要修改的節點新開一個，然后儲存每次修改后的根節點就能實現可持久化了。這樣的時間和空間復雜度都是 \(O(n\log n)\) 的。
實際上對于 \(O(n\log n)\) 這個空間上限不一定完全保證。
并且主席樹的題目空間限制都比較松，建議盡量開大一點，不是壞事。
注意可持久化線段樹不能按照下放懶標記的方式進行區間修改，因為有共用的節點。所以在可持久化線段樹上進行區間修改需要采取標記永久化的方式。具體實現如下：
void mdf(int l,int r,ll k,int s,int t,int q,int&p){
st[p=++tot]=st[q];
st[p].c+=(min(t,r)-max(s,l)+1)*k;
if(l<=s&&t<=r) return st[p].lazy+=k,void();
int mid=(s+t)>>1;
if(l<=mid) mdf(l,r,k,s,mid,lq,lp);
if(mid<r) mdf(l,r,k,mid+1,t,rq,rp);
}
ll sum(int l,int r,int s,int t,ll tag,int p){
if(l<=s&&t<=r) return st[p].c+(t-s+1)*tag;
int mid=(s+t)>>1;
ll res=0;
if(l<=mid) res+=sum(l,r,s,mid,tag+st[p].lazy,lp);
if(mid<r) res+=sum(l,r,mid+1,t,tag+st[p].lazy,rp);
return res;
}
簡單來說就是修改途中一路更改受影響的點，然后查詢途中累加一路的標記。
應用
靜態區間 k 小值
典型例題：P3834 【模板】可持久化線段樹 2。
這是主席樹的常見應用。當然整體二分也可以做，但如果強制在線就似了。下面介紹用主席樹維護的方法。
首先考慮如何求出全局 \(k\) 小值。顯然建出權值線段樹然后線段樹二分即可。
然后考慮如何求出 \([1,r]\) 的 \(k\) 小值。學會了主席樹，我們就知道建出主席樹后在 \(r\) 的根節點版本上進行線段樹二分即可。
最后考慮如何求出 \([l,r]\) 的 \(k\) 小值。這里運用了前綴和的思想，我們發現區間 \([l,r]\) 的統計信息只需用 \([1,r]\) 減去 \([1,l-1]\) 即可。于是問題得解。
constexpr int MAXN=2e5+5;
int n,m,a[MAXN],b[MAXN],rt[MAXN],tot;
struct{
#define lp st[p].lc
#define rp st[p].rc
#define lq st[q].lc
#define rq st[q].rc
struct SegTree{
int lc,rc,c;
}st[MAXN<<5];
void build(int s,int t,int&p){
p=++tot;
if(s==t) return;
int mid=(s+t)>>1;
build(s,mid,lp),build(mid+1,t,rp);
}
void chg(int x,int s,int t,int q,int&p){
st[p=++tot]=st[q];
st[p].c++;
if(s==t) return;
int mid=(s+t)>>1;
if(x<=mid) chg(x,s,mid,lq,lp);
else chg(x,mid+1,t,rq,rp);
}
int ask(int l,int r,int k,int q,int p){
if(l==r) return l;
int mid=(l+r)>>1,res=st[lp].c-st[lq].c;
if(res>=k) return ask(l,mid,k,lq,lp);
else return ask(mid+1,r,k-res,rq,rp);
}
}T;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) T.chg(read(),0,1e9,rt[i-1],rt[i]);
while(m--){
int l=read(),r=read(),k=read();
write(T.ask(0,1e9,k,rt[l-1],rt[r]));
}
return fw,0;
}
動態區間 k 小值
典型例題：P2617 Dynamic Rankings。
從靜態變為動態，如果暴力的話，單點修改位置 \(x\) 導致我們需要重構從 \(x\) 到 \(n\) 的主席樹，顯然超時。
但是由上可知，主席樹本質上維護的是前綴和信息，而上文的暴力算法本質上是暴力修改前綴和數組，然后利用前綴和數組求出我們想要的答案，所以這個問題的本質就是單點修改、區間查詢。
于是自然想到可以把樹狀數組套在這個上面優化。具體地，將樹狀數組的每一個點看作一個主席樹，修改的時候對受影響的節點正常修改即可，但查詢的時候需要先跑出所有受影響的節點，然后對應地一起作差才是正確的答案。
本質上這仍然是一種樹套樹解法，即樹狀數組套權值線段樹，但比一般的樹套樹（線段樹套平衡樹）的復雜度低一個 \(\log\)，是 \(O(n\log^2n)\) 的。
constexpr int MAXN=1e5+5;
int t,n,m,a[MAXN],rt[MAXN];
vector<int>P,Q;
struct{
#define lp st[p].lc
#define rp st[p].rc
struct SegTree{
int lc,rc,c;
}st[MAXN*300];
int tot;
void chg(int x,int k,int s,int t,int&p){
if(!p) p=++tot;
if(s==t) return st[p].c+=k,void();
int mid=(s+t)>>1;
if(x<=mid) chg(x,k,s,mid,lp);
else chg(x,k,mid+1,t,rp);
st[p].c=st[lp].c+st[rp].c;
}
int sum(int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1,res=0;
for(auto p:P) res+=st[lp].c;
for(auto p:Q) res-=st[lp].c;
if(res>=k){
for(auto&p:P) p=lp;
for(auto&p:Q) p=lp;
return sum(l,mid,k);
}else{
for(auto&p:P) p=rp;
for(auto&p:Q) p=rp;
return sum(mid+1,r,k-res);
}
}
}T;
struct{
#define lowbit(x) (x&-x)
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)) T.chg(a[x],k,0,1e9,rt[i]);
}
int ask(int l,int r,int k){
P.clear(),Q.clear();
for(int i=r;i;i-=lowbit(i)) P.emplace_back(rt[i]);
for(int i=l-1;i;i-=lowbit(i)) Q.emplace_back(rt[i]);
return T.sum(0,1e9,k);
}
}B;
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],B.add(i,1);
while(m--){
char op;
int x,y;
cin>>op>>x>>y;
if(op=='Q'){
int k;
cin>>k;
cout<<B.ask(x,y,k)<<'\n';
}else{
B.add(x,-1);
a[x]=y;
B.add(x,1);
}
}
return 0;
}
區間數顏色
典型例題：P1972 [SDOI2009] HH的項鏈。
莫隊可以離線 \(O(n\sqrt n)\) 做，樹狀數組可以離線 \(O(n\log n)\) 做，而主席樹是在線 \(O(n\log n)\) 做的。
發現對于一個區間的某個點如果有貢獻，當且僅當它在這個區間里首次出現，也就是它上次出現的位置在 \([0,l-1]\) 這個區間。所以用主席樹解決的方法就是，記錄每個數上次出現的位置，主席樹中記錄每個位置成為 “某個數上次出現的位置” 的次數，然后對于詢問區間 \([l,r]\) 只需統計第 \(r\) 棵樹和第 \(l-1\) 棵樹在 \([0,l-1]\) 范圍內權值的差就是答案。
constexpr int MAXN=1e6+5;
int n,m,lst[MAXN],rt[MAXN];
struct{
#define lp st[p].lc
#define rp st[p].rc
#define lq st[q].lc
#define rq st[q].rc
struct SegTree{
int lc,rc,c;
}st[MAXN<<5];
int tot;
void chg(int x,int s,int t,int q,int&p){
st[p=++tot]=st[q];
st[p].c++;
if(s==t) return;
int mid=(s+t)>>1;
if(x<=mid) chg(x,s,mid,lq,lp);
else chg(x,mid+1,t,rq,rp);
}
int ask(int l,int r,int s,int t,int q,int p){
if(l<=s&&t<=r) return st[p].c-st[q].c;
int mid=(s+t)>>1,res=0;
if(l<=mid) res+=ask(l,r,s,mid,lq,lp);
if(mid<r) res+=ask(l,r,mid+1,t,rq,rp);
return res;
}
}T;
int main(){
n=read();
for(int i=1,x;i<=n;i++){
x=read();
T.chg(lst[x],0,n,rt[i-1],rt[i]);
lst[x]=i;
}
m=read();
while(m--){
int u=read(),v=read();
write(T.ask(0,u-1,0,n,rt[u-1],rt[v]));
}
return fw,0;
}
其他例題
P2633 Count on a tree
樹上主席樹的板子題。我們只需先遍歷一遍整棵樹，對每個節點開一棵繼承自其父親的主席樹儲存其權值。最后統計 \([u,v]\) 路徑的答案時統計 \(w(u)+w(v)-w(l)-w(\text{fa}(l))\) 即可，其中 \(l=\operatorname{LCA}(u,v)\)。復雜度 \(O(n\log n)\)。
P3302 [SDOI2013] 森林
與上一個題相比增加了合并操作。不妨啟發式合并，每次把小的連通塊合并到大的上面去，然后暴力重構小的連通塊上所有點的主席樹和 LCA。這樣合并復雜度是 \(O(\log n)\) 的，乘上主席樹的 \(O(n\log n)\)，總復雜度 \(O(n\log^2n)\)。
注意因為我們要重構 LCA，顯然不能樹剖，只能倍增。
P3722 [AH2017/HNOI2017] 影魔
找出這個貢獻的本質是某個區間最大值 \(c\) 做出的貢獻，先預處理每個點能產生貢獻的區間，然后枚舉這個區間最大值的位置，分類討論提供貢獻的種類并分別對應出一種在線段樹上的操作。發現這種貢獻可以被前綴和，所以用主席樹維護。
P2839 [國家集訓隊] middle
對于中位數的維護，需要想到二分答案。二分這個中位數，把小于它的所有數權值記為 \(1\)，大于等于它的所有數權值記為 \(-1\)，于是對答案的判定可以轉化成一段區間的求和問題。既然我們要讓這個中位數盡量大，也就是要使得這個區間的權值和盡量小。于是對于一組詢問 \(a,b,c,d\)，最后選出的 \([l,r]\) 實際上是從區間 \([a,d]\) 中減去 \([a,b-1]\) 的最大前綴和 \([c+1,d]\) 的最大后綴得到的，這個顯然用線段樹可以維護。
但是我們不能每次都暴力建樹。發現如果對每個權值從大到小建樹，把 \(1\) 改為 \(-1\) 的總數只有 \(n\)，所以不妨用主席樹維護每個權值的線段樹，然后對于每次二分到的中位數，在它所對應的線段樹上執行上述詢問即可。
可持久化并查集
實際上就是用可持久化線段樹實現的。
考慮要記錄版本就需要用到可持久化數組，也就是需要把 \(\text{fa}\) 數組可持久化。注意到這樣就不能使用路徑壓縮，因為路徑壓縮的復雜度是均攤的，而可持久化不允許均攤復雜度，所以只能按秩合并。按秩合并有按照深度和按照大小兩種方式，兩種方式是平替的，下文采用按照深度的方式。
什么？你想用 rope 水過？算了吧，會被卡，真的。
代碼實現相當于就是把普通的數組換成了可持久化數組，可以類比一下，很好理解。
constexpr int MAXN=2e5+5;
int n,m,rt[MAXN];
struct{
#define lp st[p].lc
#define rp st[p].rc
struct SegTree{
int lc,rc,fa,dep;
}st[MAXN<<5];
int tot;
void build(int s,int t,int&p){
p=++tot;
if(s==t) return st[p].fa=s,void();
int mid=(s+t)>>1;
build(s,mid,lp),build(mid+1,t,rp);
}
void chgd(int x,int s,int t,int&p){
st[++tot]=st[p],p=tot;
if(s==t) return st[p].dep++,void();
int mid=(s+t)>>1;
if(x<=mid) chgd(x,s,mid,lp);
else chgd(x,mid+1,t,rp);
}
void chgf(int x,int k,int s,int t,int&p){
st[++tot]=st[p],p=tot;
if(s==t) return st[p].fa=k,void();
int mid=(s+t)>>1;
if(x<=mid) chgf(x,k,s,mid,lp);
else chgf(x,k,mid+1,t,rp);
}
int ask(int x,int s,int t,int p){
if(s==t) return p;
int mid=(s+t)>>1;
if(x<=mid) return ask(x,s,mid,lp);
else return ask(x,mid+1,t,rp);
}
int fnd(int x,int p){
int rt=ask(x,1,n,p);
if(st[rt].fa==x) return rt;
return fnd(st[rt].fa,p);
}
void mge(int x,int y,int p){
x=fnd(x,rt[p]),y=fnd(y,rt[p]);
if(x==y) return;
if(st[x].dep>st[y].dep) swap(x,y);
chgf(st[x].fa,st[y].fa,1,n,rt[p]);
if(st[x].dep==st[y].dep) chgd(st[y].fa,1,n,rt[p]);
}
bool chk(int x,int y,int p){
x=fnd(x,rt[p]),y=fnd(y,rt[p]);
return st[x].fa==st[y].fa;
}
}T;
int main(){
n=read(),m=read();
T.build(1,n,rt[0]);
for(int i=1;i<=m;i++){
rt[i]=rt[i-1];
int opt=read();
switch(opt){
case 1:{
int x=read(),y=read();
T.mge(x,y,i);
break;
}case 2:{
rt[i]=rt[read()];
break;
}default:{
int x=read(),y=read();
write(T.chk(x,y,i));
break;
}
}
}
return fw,0;
}
可持久化平衡樹
一般的可持久化平衡樹基于 FHQ Treap，因為它分裂和合并的操作相較于旋轉更方便于可持久化。
相較于普通平衡樹，可持久化平衡樹的 split 和 merge 操作中都需要新建節點。然后就和普通平衡樹的寫法沒什么區別了。注意它的空間復雜度并不是嚴格 \(O(n\log n)\) 的，所以能開大盡量開大，沒什么可說的。
rope 過不去的。
代碼（P3835【模板】可持久化平衡樹）：
constexpr int MAXN=5e5+5;
int n,m,rt[MAXN];
mt19937 wdz(chrono::steady_clock::now().time_since_epoch().count());
struct{
struct FHQ_Treap{
int ls,rs,key,pri,siz;
}t[MAXN<<6];
int tot;
int newnode(int x){
t[++tot].siz=1;
t[tot].key=x;
t[tot].pri=wdz();
return tot;
}
int update(int p){
t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;
return p;
}
void split(int p,int x,int&l,int&r){
if(!p) return l=r=0,void();
if(t[p].key<=x){
t[l=++tot]=t[p];
split(t[p].rs,x,t[l].rs,r);
update(l);
}else{
t[r=++tot]=t[p];
split(t[p].ls,x,l,t[r].ls);
update(r);
}
}
int mge(int l,int r){
if(!l||!r) return l|r;
int rt=++tot;
if(t[l].pri>t[r].pri){
t[rt]=t[l];
t[rt].rs=mge(t[rt].rs,r);
}else{
t[rt]=t[r];
t[rt].ls=mge(l,t[rt].ls);
}
return update(rt);
}
void ins(int q,int&p,int x){
int l,r;
split(q,x,l,r);
p=mge(mge(l,newnode(x)),r);
}
void del(int q,int&p,int x){
int l,r,w;
split(q,x,l,r);
split(l,x-1,l,w);
w=mge(t[w].ls,t[w].rs);
p=mge(mge(l,w),r);
}
int rnk(int p,int x){
int l,r;
split(p,x-1,l,r);
int res=t[l].siz+1;
p=mge(l,r);
return res;
}
int kth(int p,int k){
if(k==t[t[p].ls].siz+1) return t[p].key;
if(k<=t[t[p].ls].siz) return kth(t[p].ls,k);
return kth(t[p].rs,k-t[t[p].ls].siz-1);
}
int pre(int p,int x){
int l,r;
split(p,x-1,l,r);
int res=kth(l,t[l].siz);
p=mge(l,r);
return !l?INT_MIN+1:res;
}
int nxt(int p,int x){
int l,r;
split(p,x,l,r);
int res=kth(r,1);
p=mge(l,r);
return !r?INT_MAX:res;
}
}T;
int main(){
n=read();
for(int i=1;i<=n;i++){
int v=read(),opt=read(),x=read();
rt[i]=rt[v];
switch(opt){
case 1:{
T.ins(rt[i],rt[i],x);
break;
}case 2:{
T.del(rt[i],rt[i],x);
break;
}case 3:{
write(T.rnk(rt[i],x));
break;
}case 4:{
write(T.kth(rt[i],x));
break;
}case 5:{
write(T.pre(rt[i],x));
break;
}default:{
write(T.nxt(rt[i],x));
break;
}
}
}
return fw,0;
}
應用
P5055 【模板】可持久化文藝平衡樹
比普通的可持久化平衡樹多了一個懶標記，只需在下放標記的時候把左右兒子復制一遍即可。
rope 可水過。
constexpr int MAXN=2e5+5;
int n,m,rt[MAXN];
mt19937 wdz(chrono::steady_clock::now().time_since_epoch().count());
struct{
struct FHQ_Treap{
int ls,rs,key,pri,siz,lazy;
ll sum;
}t[MAXN<<7];
int tot;
int newnode(int x){
t[++tot].siz=1;
t[tot].key=t[tot].sum=x;
t[tot].pri=wdz();
return tot;
}
int update(int p){
t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;
t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].key;
return p;
}
void pushdown(int p){
if(!t[p].lazy) return;
if(t[p].ls) t[++tot]=t[t[p].ls],t[p].ls=tot;
if(t[p].rs) t[++tot]=t[t[p].rs],t[p].rs=tot;
swap(t[p].ls,t[p].rs);
t[t[p].ls].lazy^=1;
t[t[p].rs].lazy^=1;
t[p].lazy=0;
}
void split(int p,int x,int&l,int&r){
if(!p) return l=r=0,void();
pushdown(p);
if(t[t[p].ls].siz+1<=x){
t[l=++tot]=t[p];
split(t[p].rs,x-t[t[p].ls].siz-1,t[l].rs,r);
update(l);
}else{
t[r=++tot]=t[p];
split(t[p].ls,x,l,t[r].ls);
update(r);
}
}
int mge(int l,int r){
if(!l||!r) return l|r;
pushdown(l),pushdown(r);
int rt=++tot;
if(t[l].pri>t[r].pri){
t[rt]=t[l];
t[rt].rs=mge(t[rt].rs,r);
}else{
t[rt]=t[r];
t[rt].ls=mge(l,t[rt].ls);
}
return update(rt);
}
void ins(int q,int&p,int x,int y){
int l,r;
split(q,x,l,r);
p=mge(mge(l,newnode(y)),r);
}
void del(int q,int&p,int x){
int l,r,w;
split(q,x,l,r);
split(l,x-1,l,w);
w=mge(t[w].ls,t[w].rs);
p=mge(mge(l,w),r);
}
void flp(int&p,int x,int y){
int l,r,w;
split(p,x-1,l,r);
split(r,y-x+1,w,r);
t[w].lazy^=1;
p=mge(mge(l,w),r);
}
ll ask(int p,int x,int y){
int l,r,w;
split(p,x-1,l,r);
split(r,y-x+1,w,r);
ll res=t[w].sum;
p=mge(mge(l,w),r);
return res;
}
}T;
int main(){
n=read();
ll lst=0;
for(int i=1,v,opt,x,y;i<=n;i++){
v=read(),opt=read(),x=read()^lst;
if(opt!=2) y=read()^lst;
rt[i]=rt[v];
switch(opt){
case 1:{
T.ins(rt[i],rt[i],x,y);
break;
}case 2:{
T.del(rt[i],rt[i],x);
break;
}case 3:{
T.flp(rt[i],x,y);
break;
}default:{
write(lst=T.ask(rt[i],x,y));
break;
}
}
}
return fw,0;
}
[HDU6087] Rikka with Sequence
多出了一個操作 2，實際上對于操作 2 l r k 相當于把 \([l-k,l-1]\) 這個區間一直復制，直到填滿 \([l-k,r]\) 這個區間。可以考慮倍增優化它。至于坑人的 64MiB 空間，需要我們在節點數量過大的時候暴力重構整棵平衡樹，同時還要進行內存回收。
還有需要注意的是，這題因為使用倍增優化，導致它的重復合并次數比較多，如果使用正常的隨機權值方法來合并會掛掉，所以只能采用一種特殊的方式來合并它，具體見代碼。但是在正常的題目中，這樣寫的復雜度不一定更優。
using ll=long long;
constexpr int MAXN=2e5+5;
int n,m,a[MAXN],rt[2];
mt19937 wdz(chrono::steady_clock::now().time_since_epoch().count());
struct{
struct FHQ_Treap{
int ls,rs,key,siz;
ll sum;
}t[MAXN<<3];
int tot,tim;
int stk[MAXN<<3],top;
int used[MAXN<<3],cnt;
int vis[MAXN<<3];
int newnode(int x=0){
int tt=(top?stk[top--]:++tot);
used[++cnt]=tt;
t[tt].ls=t[tt].rs=0;
t[tt].siz=1;
t[tt].key=t[tt].sum=x;
return tt;
}
int update(int p){
t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;
t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].key;
return p;
}
void split(int p,int x,int&l,int&r){
if(!p) return l=r=0,void();
if(t[t[p].ls].siz+1<=x){
l=newnode();
t[l]=t[p];
split(t[p].rs,x-t[t[p].ls].siz-1,t[l].rs,r);
update(l);
}else{
r=newnode();
t[r]=t[p];
split(t[p].ls,x,l,t[r].ls);
update(r);
}
}
int mge(int l,int r){
if(!l||!r) return l|r;
int rt=newnode();
if(wdz()%(t[l].siz+t[r].siz)<t[l].siz){
t[rt]=t[l];
t[rt].rs=mge(t[rt].rs,r);
}else{
t[rt]=t[r];
t[rt].ls=mge(l,t[rt].ls);
}
return update(rt);
}
int build(int l,int r){
if(l>r) return 0;
int mid=(l+r)>>1,rt=newnode(a[mid]);
t[rt].ls=build(l,mid-1);
t[rt].rs=build(mid+1,r);
return update(rt);
}
void dfs(int u){
if(!u) return;
vis[u]=tim;
dfs(t[u].ls),dfs(t[u].rs);
}
void rebuild(){
tim++;
dfs(rt[0]),dfs(rt[1]);
int ntot=0;
for(int i=1;i<=cnt;i++)
if(vis[used[i]]!=tim) stk[++top]=used[i];
else used[++ntot]=used[i];
cnt=ntot;
}
ll ask(int p,int x,int y){
int l,r,w;
split(p,x-1,l,r);
split(r,y-x+1,w,r);
ll res=t[w].sum;
p=mge(mge(l,w),r);
return res;
}
void mdf(int&p,int x,int y,int k){
int r1,r2,r3,r4,r5,r6;
split(p,y,r1,r4);
split(r1,x-1,r1,r3);
split(r1,x-k-1,r1,r2);
r5=r2,r3=0;
int b=(y-x+1)/k+1;
while(b){
if(b&1) r3=mge(r3,r5);
r5=mge(r5,r5);
b>>=1;
}
split(r3,y-x+1,r3,r6);
p=mge(mge(mge(r1,r2),r3),r4);
}
void cpy(int q,int&p,int x,int y){
int r1,r2,r3,r4,r5,r6;
split(q,y,r1,r3);
split(r1,x-1,r1,r2);
split(p,y,r4,r6);
split(r4,x-1,r4,r5);
p=mge(mge(r4,r2),r6);
}
}T;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
rt[0]=rt[1]=T.build(1,n);
while(m--){
int op=read(),x=read(),y=read();
switch(op){
case 1:{
write(T.ask(rt[1],x,y));
break;
}case 2:{
T.mdf(rt[1],x,y,read());
break;
}default:{
T.cpy(rt[0],rt[1],x,y);
break;
}
}
if(T.cnt>=1.5e6) T.rebuild();
}
return fw,0;
}
可持久化字典樹
和上面兩種結構的可持久化方式基本一致。在一次修改中，對于需要修改的節點進行修改，沒有動的節點繼續復用之前的節點即可。
可持久化字典樹的主要應用就是求最大異或和問題。具體來說，這類問題的形式為：給定一個數列和 \(l,r,x\)，求 \(\max\limits_{l\le k\le r}\{a_k\oplus x\}\)。所以可持久化字典樹中需要給每個節點記錄一個 \(\mathit{val}\) 值表示當前點被多少個版本使用，從而在查詢的時候直接相減即可。
代碼：（P4735 最大異或和）
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=6e5+5;
int n,m,a[MAXN],rt[MAXN];
struct{
struct Trie{
int c[2],val;
int& operator[](int x){
return c[x];
}
}t[MAXN<<5];
int tot;
void ins(int x,int q,int p){
for(int i=25;~i;i--){
int c=x>>i&1;
if(!t[p][c]) t[p][c]=++tot;
t[p][!c]=t[q][!c];
t[p].val=t[q].val+1;
p=t[p][c],q=t[q][c];
}
t[p].val=t[q].val+1;
}
int ask(int x,int q,int p){
int res=0;
for(int i=25;~i;i--){
int c=x>>i&1;
if(t[t[p][!c]].val-t[t[q][!c]].val) res+=1<<i,p=t[p][!c],q=t[q][!c];
else p=t[p][c],q=t[q][c];
}
return res;
}
}T;
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]^=a[i-1];
rt[i]=++T.tot;
T.ins(a[i],rt[i-1],rt[i]);
}
while(m--){
char c;
cin>>c;
if(c=='A'){
cin>>a[++n];
a[n]^=a[n-1];
rt[n]=++T.tot;
T.ins(a[n],rt[n-1],rt[n]);
}else{
int l,r,x;
cin>>l>>r>>x;
l--,r--;
if(!l) cout<<max(a[n]^x,T.ask(a[n]^x,rt[0],rt[r]))<<'\n';
else cout<<T.ask(a[n]^x,rt[l-1],rt[r])<<'\n';
}
}
return 0;
}
應用
P4098 [HEOI2013] ALO
重點是如何找出一個區間的次大值。顯然不好做，套路地轉化為針對每個數求其作為次大值的區間。這里方法比較多，比較簡單的實現方式是使用鏈表，從小到大依次刪數，那么到某個數時比它小的數一定都已被刪完，我們就可以方便地求出其向左或向右第一個和第二個比它大的數的位置。不妨從左到右依次記為 \(l_2,l_1,r_1,r_2\)，容易發現使當前數為區間最大值的極大區間為 \((l_2,r_1)\) 和 \((l_1,r_2)\)，分別在這兩個區間求最大異或和即可。
P10690 Fotile 模擬賽 L
考慮分塊，預處理每個塊中的最大連續異或和。塊與塊之間顯然可以 \(O(1)\) 轉移。然后對于每個詢問中的散塊暴力，整塊直接獲取答案，求最大值即可。只要對可持久化字典樹有充分理解就很簡單。
P5795 [THUSC 2015] 異或運算
發現題目中 \(n,p\) 的數據范圍是一個 \(O(n^2)\) 復雜度，啟示我們要暴力枚舉每一行的貢獻。然后發現求區間 \(k\) 大值，考慮可持久化字典樹上二分。具體來說，為了答案盡可能大，就是先判斷與當前位不同的一邊的 \(\mathit{val}\) 值之和，如果比 \(k\) 大說明這一位可以提供貢獻，累加貢獻然后掃這一邊；否則掃另一邊。注意在同一時刻每行的根可能是不同的，所以需要給每行開一個數組記錄當前行的根。
浙公網安備 33010602011771號