「Note」数据结构方向 - 数据结构进阶
1. 平衡樹（FHQ-Treap）
1.1. 介紹
功能強大的平衡樹，以至于我根本沒學(xué) Treap 以及 Splay（LCT 里的另談），缺點就大概是常數(shù)大。
FHQ-Treap 核心操作在于分裂與合并。
因為合并時按照隨機權(quán)值決定父子關(guān)系，期望復(fù)雜度為 \(\log n\)。
1.1.1 分裂
按照權(quán)值 \(val\) 分裂，給定 \(val\)，將整棵平衡樹 \(T\) 分裂為 \(T_x,T_y\) 使得 \(\forall i\in T_x,\forall j\in T_y\)，有 \(val_i\le val<val_j\)。
對于當(dāng)前節(jié)點 \(rt\)，若 \(val_rt\le val\)，則左子樹以及 \(rt\) 都應(yīng)分到 \(T_x\) 中，故只需向右遞歸右子節(jié)點；反之類似地遞歸左子節(jié)點。
void split(int rt,int &x,int &y,int val)
{
if(!rt){x=y=0;return;}
if(t[rt].val<=val)split(t[rt].rs,t[x=rt].rs,y,val);
else split(t[rt].ls,x,t[y=rt].ls,val);
push_up(rt);
return;
}
其中 push_up() 函數(shù)是用來更新節(jié)點信息的，一定不要忘寫。
1.1.2 合并
給定兩棵樹 \(T_x,T_y\)，前提是 \(\forall i\in T_x,\forall j\in T_y\)，有 \(val_i<val_j\)。
對于要合并的 \(x,y\)，我們根據(jù)優(yōu)先級決定父子關(guān)系，根據(jù) \(val_x<val_y\) 調(diào)用 merge() 合并對應(yīng)子節(jié)點。
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].key<t[y].key){t[x].rs=merge(t[x].rs,y);push_up(x);return x;}
t[y].ls=merge(x,t[y].ls);
push_up(y);
return y;
}
1.2. 其他功能
1.2.1. 插入值
按照 \(val-1\) 分裂為兩棵樹，再新建節(jié)點合并即可。
void ins(int val)
{
int x=0,y=0;
split(root,x,y,val-1);
root=merge(merge(x,new_node(val)),y);
return;
}
其中 new_node() 函數(shù)用于新建節(jié)點，返回節(jié)點編號，\(\mathrm{root}\) 為整棵平衡樹的根。
1.2.2. 刪除值（只刪一個）
void del(int val)
{
int x=0,y=0,z=0;
split(root,x,z,val),split(x,x,y,val-1);
root=merge(merge(x,y=merge(t[y].ls,t[y].rs)),z);
return;
}
1.2.3. 查詢值的排名
按照 \(val-1\) 分裂為 \(T_x,T_y\)，\(siz_x+1\) 即答案，記得合并回來。
int rk(int val)
{
int x=0,y=0,res=0;
split(root,x,y,val-1);
res=t[x].siz+1;
root=merge(x,y);
return res;
}
1.2.4. 查詢第 \(k\) 大
類似線段樹上二分，若 \(k\le siz_{ls_{rt}}\) 則向左子節(jié)點遞歸，若 \(k=siz_{ls_{rt}}+1\) 則返回 \(val_{rt}\)，否則向右子節(jié)點遞歸。
int kth(int k)
{
int now=root;
while(true)
{
if(k<=t[t[now].ls].siz)now=t[now].ls;
else if(k==t[t[now].ls].siz+1)return t[now].val;
else k-=t[t[now].ls].siz+1,now=t[now].rs;
}
}
1.2.5. 查找嚴(yán)格小于 / 大于 \(val\) 的前驅(qū) / 后繼
類似二分（可能），與上一過程類似。也可以采用分裂后找值。
int pre(int val)
{
int now=root,res=0;
while(true)
{
if(!now)return res;
if(val<=t[now].val)now=t[now].ls;
else res=t[now].val,now=t[now].rs;
}
}
int suf(int val)
{
int now=root,res=0;
while(true)
{
if(!now)return res;
if(val>=t[now].val)now=t[now].rs;
else res=t[now].val,now=t[now].ls;
}
}
1.2.6. 區(qū)間翻轉(zhuǎn)
此操作要求維護序列平衡樹，考慮維護每個位置的值，此時平衡樹并不需要滿足二叉搜索樹性質(zhì)。
修改時將修改區(qū)間按照 \(siz\) 分離出來，打翻轉(zhuǎn)標(biāo)記即可。
1.3. 例題
\(\color{royalblue}{P3369}\)
$\text{Code}$：
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
inline int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
//--------------------//
const int N=1e5+5;
int n;
//--------------------//
struct FHQ_Treap
{
struct FHQ_Treap_Node
{
int siz,val,key;
int ls,rs;
}t[N];
int tot,root;
int new_node(int val)
{
t[++tot].val=val;
t[tot].key=rand();
t[tot].siz=1;
return tot;
}
void push_up(int rt)
{
t[rt].siz=t[t[rt].ls].siz+t[t[rt].rs].siz+1;
return;
}
void split(int rt,int &x,int &y,int v)
{
if(!rt){x=y=0;return;}
if(t[rt].val<=v)split(t[rt].rs,t[x=rt].rs,y,v);
else split(t[rt].ls,x,t[y=rt].ls,v);
push_up(rt);
return;
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].key<t[y].key){t[x].rs=merge(t[x].rs,y);push_up(x);return x;}
t[y].ls=merge(x,t[y].ls);
push_up(y);
return y;
}
void ins(int val)
{
int x=0,y=0;
split(root,x,y,val-1);
root=merge(merge(x,new_node(val)),y);
return;
}
void del(int val)
{
int x=0,y=0,z=0;
split(root,x,z,val),split(x,x,y,val-1);
root=merge(merge(x,y=merge(t[y].ls,t[y].rs)),z);
return;
}
int rk(int val)
{
int x=0,y=0,res=0;
split(root,x,y,val-1);
res=t[x].siz+1;
root=merge(x,y);
return res;
}
int kth(int k)
{
int now=root;
while(true)
{
if(k<=t[t[now].ls].siz)now=t[now].ls;
else if(k==t[t[now].ls].siz+1)return t[now].val;
else k-=t[t[now].ls].siz+1,now=t[now].rs;
}
}
int pre(int val)
{
int now=root,res=0;
while(true)
{
if(!now)return res;
if(val<=t[now].val)now=t[now].ls;
else res=t[now].val,now=t[now].rs;
}
}
int suf(int val)
{
int now=root,res=0;
while(true)
{
if(!now)return res;
if(val>=t[now].val)now=t[now].rs;
else res=t[now].val,now=t[now].ls;
}
}
}F;
//--------------------//
int main()
{
n=rd();
for(int op,x,i=1;i<=n;i++)
{
op=rd(),x=rd();
if(op==1)F.ins(x);
else if(op==2)F.del(x);
else if(op==3)printf("%d\n",F.rk(x));
else if(op==4)printf("%d\n",F.kth(x));
else if(op==5)printf("%d\n",F.pre(x));
else printf("%d\n",F.suf(x));
}
return 0;
}
\(\color{royalblue}{P3391}\)
板子。
$\text{Code}$：
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e5+5;
struct FHQ_Treap
{
struct FHQ_Treap_Node
{
int val,siz,ls,rs,key;
bool lazy;
}t[N];
int root,tot;
int new_node(int val)
{
t[++tot]={val,1,0,0,rand(),false};
return tot;
}
void tag(int rt)
{
swap(t[rt].ls,t[rt].rs);
t[rt].lazy^=1;
return;
}
void push_up(int rt)
{
t[rt].siz=t[t[rt].ls].siz+t[t[rt].rs].siz+1;
return;
}
void push_down(int rt)
{
if(!t[rt].lazy)
return;
tag(t[rt].ls);
tag(t[rt].rs);
t[rt].lazy^=1;
return;
}
void split(int rt,int &x,int &y,int siz)
{
if(!rt){x=y=0;return;}
push_down(rt);
if(t[t[rt].ls].siz>=siz)split(t[rt].ls,x,t[y=rt].ls,siz);
else split(t[rt].rs,t[x=rt].rs,y,siz-t[t[rt].ls].siz-1);
push_up(rt);
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
push_down(x),push_down(y);
if(t[x].key<t[y].key){t[x].rs=merge(t[x].rs,y);push_up(x);return x;}
t[y].ls=merge(x,t[y].ls);
push_up(y);
return y;
}
void change(int l,int r)
{
int x,y,z;
split(root,x,z,r);
split(x,x,y,l-1);
tag(y);
root=merge(x,merge(y,z));
return;
}
void Tprint(int rt)
{
if(!rt)
return;
push_down(rt);
Tprint(t[rt].ls);
printf("%d ",t[rt].val);
Tprint(t[rt].rs);
return;
}
}T;
int n,m;
//--------------------//
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
T.root=T.merge(T.root,T.new_node(i));
for(int l,r,i=1;i<=m;i++)
scanf("%d%d",&l,&r),T.change(l,r);
T.Tprint(T.root);
return 0;
}
2. 樹套樹
3.1. 介紹
樹套樹可以用來維護二維的信息。
顧名思義，樹套樹就是一個數(shù)據(jù)結(jié)構(gòu)套上另一個數(shù)據(jù)結(jié)構(gòu)，一般來講內(nèi)部維護的信息都需要可合并，通過外層數(shù)據(jù)結(jié)構(gòu)合并內(nèi)層信息來達(dá)到維護二維信息的目的。
內(nèi)層數(shù)據(jù)結(jié)構(gòu)需要滿足動態(tài)開點，外層數(shù)據(jù)結(jié)構(gòu)如果可行則采用樹狀數(shù)組維護以減小常數(shù)，一般情況下樹狀數(shù)組套線段樹較為通用。
3.2. 常用技巧
3.2.1. 動態(tài)的區(qū)間內(nèi)偏序問題
樹狀數(shù)組維護一維，線段樹維護另一維，在符合第一維要求的樹狀數(shù)組上查詢第二維符合要求的信息，修改是簡單的。
3.2.2. 動態(tài)第 \(k\) 小
靜態(tài)第 \(k\) 小采用可持久化線段樹，每一個位置都繼承前一位置的信息，然后前綴相減。
動態(tài)第 \(k\) 小只要在樹狀數(shù)組的維護方式上進行繼承信息即可。
3. LCT
3.1. 介紹
3.1.1. 基本概念
LCT 全名 Link-Cut-Tree，動態(tài)樹，是用來維護動態(tài)森林的數(shù)據(jù)結(jié)構(gòu)。
它支持以下操作（需要保證任意操作時刻維護的都為森林）：
- 連邊。
- 斷邊。
- 換根。
- 提取路徑信息。
LCT 的大體思路是將每棵樹拆分為若干條鏈，并用平衡樹維護鏈中節(jié)點，維護關(guān)鍵字為節(jié)點深度，每一條鏈的狀態(tài)都是動態(tài)的。
由于 LCT 結(jié)構(gòu)的特殊性，一般我們用 Splay 維護鏈，更加抽象的，我們實際上并不直接利用類似 \(\mathrm{build}\) 的東西將樹劃分成若干鏈，我們在需要的時候動態(tài)維護我們需要的鏈，這基于了 Splay 方便的各種操作。
在維護的時候，對于每一個節(jié)點，我們選出至多一個兒子作為實兒子，令節(jié)點到實兒子的邊為實邊，剩余邊為虛邊。實邊組成的鏈成為實鏈，因為實鏈?zhǔn)俏覀兯x擇的，所以 LCT 的才是靈活多變的，請牢記我們的實鏈?zhǔn)遣粩嘧兓ゾS護信息的。
3.1.2. 輔助樹
我們用 Splay 以節(jié)點深度為關(guān)鍵字維護每條實鏈上的點，虛邊連接了一棵棵 Splay，每個 Splay 的根節(jié)點都有一條虛邊指向其維護原鏈頂?shù)?strong>父節(jié)點。以這樣的方式連接，一棵樹上的多個 Splay 就組成了一棵輔助樹，多棵輔助樹就構(gòu)成了我們的 LCT。
一顆輔助樹有如下性質(zhì)：
- 中序遍歷每棵 Splay 得到的點序列，對應(yīng)其維護鏈從上至下的一條路徑。
- 輔助樹節(jié)點與原樹節(jié)點一一對應(yīng)。
- 每棵 Splay 根節(jié)點父節(jié)點并不為空，其用虛邊指向了此 Splay 維護原鏈的父節(jié)點。需要注意的，根節(jié)點并不是其父節(jié)點的子節(jié)點（認(rèn)父不認(rèn)子）。
由于輔助樹的以上性質(zhì)，我們?nèi)魏尾僮鞫疾恍枰S護原樹，輔助樹可以在任何情況下提取出一棵原樹。
需要注意的：
- 原樹的根不等于輔助樹的根，原樹的父節(jié)點指向不等于輔助樹的父節(jié)點指向。
- 虛實鏈?zhǔn)强梢栽谳o助樹上進行變換，實現(xiàn)了動態(tài)的樹鏈剖分，這也是前文說到的“實鏈?zhǔn)遣粩嘧兓ゾS護信息的”。
至于為什么在操作過程中需要翻轉(zhuǎn) Splay，目的是保證復(fù)雜度，具體證明大概是論文級的，這里不會提及，只需要記住即可。
3.1.3 實現(xiàn)過程
以洛谷模板題為例，進行實現(xiàn)過程的講解。
維護一個結(jié)構(gòu)體表示一個節(jié)點，其中含有以下信息：
| \(fa\) | \(son_{1/0}\) | \(val\) | \(sum\) | \(siz\) | \(lazy\) |
|---|---|---|---|---|---|
| 父節(jié)點 | 子節(jié)點 | 此節(jié)點權(quán)值 | 此節(jié)點在 Splay 中的子樹異或和 | 此節(jié)點在 Splay 中的子樹大小 | 翻轉(zhuǎn)標(biāo)記 |
介紹 LCT 的核心函數(shù)之前先給出兩個 Splay 的函數(shù)（\(t\) 是我們的節(jié)點結(jié)構(gòu)體數(shù)組）。
void rotate(int rt)
{
int fa=t[rt].fa,gfa=t[fa].fa,gs=get(rt),gfs=get(fa);
bool flag=che_rt(fa);
t[fa].son[gs]=t[rt].son[!gs],t[t[rt].son[!gs]].fa=fa;
t[rt].son[!gs]=fa,t[fa].fa=rt,t[rt].fa=gfa;
if(!flag)
t[gfa].son[gfs]=rt;
push_up(fa),push_up(rt);
return;
}
void splay(int rt)
{
push_down_(rt);
for(int now=t[rt].fa;!che_rt(rt);rotate(rt))
if(!che_rt(now=t[rt].fa))
rotate((get(now)==get(rt))?now:rt);
return;
}
rotate（） 函數(shù)進行單旋操作，splay() 函數(shù)將節(jié)點旋至其所在 Splay 的根節(jié)點。與正常 Splay 不同的是，我們需要判斷一個節(jié)點是否為其所在 Splay 的根（che_rt() 函數(shù)的作用），同時也請注意翻轉(zhuǎn)標(biāo)記的下傳。
接下來我們介紹 LCT 的核心操作。
void access(int rt)
{
for(int lst=0;rt;lst=rt,rt=t[rt].fa)
{
splay(rt);
t[rt].son[1]=lst;
push_up(rt);
}
return;
}
此函數(shù)作用是把某節(jié)點到當(dāng)前輔助樹的根路徑上的點合并為一棵新的 Splay，具體過程如下：
- 現(xiàn)將當(dāng)前節(jié)點旋至其所在 Splay 的根。
- 將上一節(jié)點接到當(dāng)前節(jié)點上（這樣直接實現(xiàn)了新鏈的合并與原來 Splay 邊的斷開）。
- 更新當(dāng)前節(jié)點信息。
- 跳轉(zhuǎn)到父親，重復(fù)操作直到跳至根。
我們的剩余函數(shù)都以 access() 函數(shù)為基礎(chǔ)進行操作，接下來介紹其他的函數(shù)。
tag()用于對節(jié)點打上旋轉(zhuǎn)標(biāo)記。
void tag(int rt)
{
swap(t[rt].son[0],t[rt].son[1]);
t[rt].lazy^=1;
return;
}
che_rt()用于檢查節(jié)點是否為 Splay 的根。
bool che_rt(int rt)
{
return (t[t[rt].fa].son[0]!=rt&&t[t[rt].fa].son[1]!=rt);
}
get()用于找到當(dāng)前節(jié)點是其父節(jié)點的哪個兒子。
int get(int rt)
{
return ((t[t[rt].fa].son[1]==rt)?1:0);
}
push_up()更新當(dāng)前節(jié)點信息。
void push_up(int rt)
{
t[rt].siz=t[t[rt].son[0]].siz+t[t[rt].son[1]].siz+1;
t[rt].sum=t[t[rt].son[0]].sum^t[t[rt].son[1]].sum^t[rt].val;
return;
}
push_down()下傳標(biāo)記。
void push_down(int rt)
{
if(t[rt].lazy!=0)
{
tag(t[rt].son[0]);
tag(t[rt].son[1]);
t[rt].lazy=0;
}
return;
}
push_down_()下傳當(dāng)前節(jié)點至 Splay 根節(jié)點的標(biāo)記（從上至下）。
void push_down_(int rt)
{
if(!che_rt(rt))
push_down_(t[rt].fa);
push_down(rt);
}
make_rt()使當(dāng)前節(jié)點變?yōu)檩o助樹的根。
void make_rt(int rt)
{
access(rt);
splay(rt);
tag(rt);
return;
}
find_rt()查詢當(dāng)前節(jié)點所在輔助樹的根（請考慮splay()的過程，不難得出結(jié)論）。
int find_rt(int rt)
{
access(rt);
splay(rt);
while(t[rt].son[0])
{
push_down(rt);
rt=t[rt].son[0];
}
splay(rt);
return rt;
}
check()查詢兩節(jié)點是否連通。
bool check(int x,int y)
{
make_rt(x);
return (find_rt(y)==x);
}
link()連邊（先判連通）。
void link(int x,int y)
{
if(!check(x,y))
t[x].fa=y;
}
cut()斷邊（判相連，仍然考慮實現(xiàn)過程即可理解）。
void cut(int x,int y)
{
if(check(x,y)&&t[x].siz<=2)
t[y].fa=t[x].son[1]=0;
}
split()分離一條鏈，正是前文提到的“提取路徑信息”。
int split(int x,int y)
{
make_rt(x);
access(y);
splay(y);
return y;
}
change()單點修改（并不是所有的題都有）。
void change(int rt,int val)
{
splay(rt);
t[rt].val=val;
push_up(rt);
return;
}
對于模板題的構(gòu)建至此結(jié)束，LCT 的拓展性較強，具體題目還需具體分析。
3.2. 常用技巧
3.2.1 基礎(chǔ)技巧
對于維護操作應(yīng)多考慮優(yōu)化，可以復(fù)雜化 push_up() 函數(shù)，但要注意代碼結(jié)構(gòu)的簡潔性，并盡可能減少代碼量與數(shù)據(jù)結(jié)構(gòu)的操作難度，即使可能使復(fù)雜度變?yōu)樯粤樱ㄔ跓o風(fēng)險前提下）。
3.2.？咕咕咕
咕咕咕
3.3. 題目
\(\color{blueviolet}{P3690}\)
板子。
$\text{Code}$：
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e5+5;
struct LCT
{
struct Tree_Node
{
int fa,son[2];
int val,sum,siz;
int lazy;
}t[N];
void tag(int rt)
{
swap(t[rt].son[0],t[rt].son[1]);
t[rt].lazy^=1;
return;
}
bool che_rt(int rt)
{
return (t[t[rt].fa].son[0]!=rt&&t[t[rt].fa].son[1]!=rt);
}
int get(int rt)
{
return ((t[t[rt].fa].son[1]==rt)?1:0);
}
void push_up(int rt)
{
t[rt].siz=t[t[rt].son[0]].siz+t[t[rt].son[1]].siz+1;
t[rt].sum=t[t[rt].son[0]].sum^t[t[rt].son[1]].sum^t[rt].val;
return;
}
void push_down(int rt)
{
if(t[rt].lazy!=0)
{
tag(t[rt].son[0]);
tag(t[rt].son[1]);
t[rt].lazy=0;
}
return;
}
void push_down_(int rt)
{
if(!che_rt(rt))
push_down_(t[rt].fa);
push_down(rt);
}
void rotate(int rt)
{
int fa=t[rt].fa,gfa=t[fa].fa;
int gs=get(rt),gfs=get(fa);
bool flag=che_rt(fa);
t[fa].son[gs]=t[rt].son[!gs];
t[t[rt].son[!gs]].fa=fa;
t[rt].son[!gs]=fa;
t[fa].fa=rt;
t[rt].fa=gfa;
if(!flag)
t[gfa].son[gfs]=rt;
push_up(fa),push_up(rt);
return;
}
void splay(int rt)
{
push_down_(rt);
for(int now=t[rt].fa;!che_rt(rt);rotate(rt))
if(!che_rt(now=t[rt].fa))
rotate((get(now)==get(rt))?now:rt);
return;
}
void access(int rt)
{
for(int lst=0;rt;lst=rt,rt=t[rt].fa)
{
splay(rt);
t[rt].son[1]=lst;
push_up(rt);
}
return;
}
void make_rt(int rt)
{
access(rt);
splay(rt);
tag(rt);
return;
}
int find_rt(int rt)
{
access(rt);
splay(rt);
while(t[rt].son[0])
{
push_down(rt);
rt=t[rt].son[0];
}
splay(rt);
return rt;
}
bool check(int x,int y)
{
make_rt(x);
return (find_rt(y)==x);
}
void link(int x,int y)
{
if(!check(x,y))
t[x].fa=y;
}
void cut(int x,int y)
{
if(check(x,y)&&t[x].siz<=2)
t[y].fa=t[x].son[1]=0;
}
int split(int x,int y)
{
make_rt(x);
access(y);
splay(y);
return y;
}
void change(int rt,int val)
{
splay(rt);
t[rt].val=val;
push_up(rt);
return;
}
}L;
//--------------------//
int n,m;
//--------------------//
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&L.t[i].val);//L.t[i].sum=L.t[i].val;
for(int op,x,y,i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&x,&y);
if(op==0)
printf("%d\n",L.t[L.split(x,y)].sum);
else if(op==1)
L.link(x,y);
else if(op==2)
L.cut(x,y);
else
L.change(x,y);
}
return 0;
}
總結(jié)
以上是生活随笔為你收集整理的「Note」数据结构方向 - 数据结构进阶的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 完美关系中DL在争取飞扬集团小力士奶粉中
- 下一篇： 深入探讨控制反转（IOC）与依赖注入（D