【数据结构】平衡树之FHQ-Treap
CNS_5t0_0r2 · · 算法·理论
请保证你有 BST 的基础再阅读本文。
本文只讲解 FHQ-Treap(我最喜欢用的平衡树,主要是觉得 Splay 代码太难写所以不想写了)。
【0】引入
众所周知,BST 在极端情况下会退化成单次操作
所以,可以对每个点随机赋一个权值。但这还不够,我们还得让节点按照随机权值排一个序(这种操作并没有破坏 BST 的性质)。Treap 的实现方法就是让随机权值满足堆的性质(下文中的 FHQ-Treap 满足大根堆的性质)来实现单次复杂度
【1】FHQ-Treap 维护集合
【1.1】FHQ-Treap 的两个基本操作:split
和 merge
无论是维护集合还是维护序列,FHQ-Treap 都是基于这两个操作实现的,这其中不需要旋转,所以 FHQ-Treap 又叫“无旋 Treap”。
【1.1.1】split
操作
split
有两种:按排名分裂和按数值分裂。维护集合用到的是后者。
按数值分裂的定义:split(u,x,&L,&R)
的定义是将以 u
为根的子树分裂成值不超过和超过 x
的两棵子树并返回两棵子树的根 L,R
。
分类讨论。当当前根 u
的权值不大于 x
时,显然整个左子树都应该分到分裂后的左子树,则 L = u
。进入右子树时,会把右子树也分裂成两个子树。其中不大于 x
的子树(根设为 v
)应该和 u
分裂后的左子树包含在同一个子树中,所以 v
应作为 u
的右儿子,即在进入右子树的时候传入 t[u].rc
的指针。
反过来同理。
这样分裂出来的两个子树显然也满足 FHQ-Treap 的性质(即随机权值满足大根堆的性质),因为任意两节点如果分裂到同一棵子树中,祖先-子孙关系不变。
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x,右子树所有节点权值 > x
if(u == 0){
L = R = 0;
return;
}
if(t[u].val <= x){
L = u;
split(t[u].rc,x,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
【1.1.2】merge
操作
merge
操作是 split
操作的逆操作,所以 merge
操作要求左子树的最大值小于右子树的最小值。在此基础上,我们要保证随机权值满足堆的性质。
设需要合并的两棵子树的根为 u
和 v
,如果 u
的随机权值大于 v
,那么 v
应该在 u
的右子树中。但是这会挤占原来 u
的右子节点的位置,所以应该合并 u
的右子树和以 v
为根的子树,并把这棵合并后的子树作为 u
的右子树,合并后的根即为 u
。
反过来同理。
/*合并的前提条件:
1. 保证 t[u].val <= t[v].val
2. 一个子树中的最大值小于另一个子树中的最小值
*/
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
以下是模版题的代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct node{
int val,pri;
int lc,rc;
int siz;
} t[N];
int node_cnt,root;
void push_up(int u){
t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x,右子树所有节点权值 > x
if(u == 0){
L = R = 0;
return;
}
if(t[u].val <= x){
L = u;
split(t[u].rc,x,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
/*合并的前提条件:
1. 保证 t[u].val <= t[v].val
2. 一个子树中的最大值小于另一个子树中的最小值
*/
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
void new_node(int x){
t[++node_cnt] = (node){x,rand() * rand(),0,0,1};
}
void insert(int x){
int u,v;
split(root,x,u,v);
new_node(x);
root = merge(merge(u,node_cnt),v);
}
void remove(int x){
int u,v,w;
split(root,x,u,v);//分裂成 <= x 的子树和 > x 的子树
split(u,x - 1,u,w);//分裂成 < x 的子树和 == x 的子树
w = merge(t[w].lc,t[w].rc);//合并 w(== x 的子树) 的左右子树 ,相当于删除了一个 x
root = merge(merge(u,w),v);
}
int rnk(int x){
int u,v;
split(root,x - 1,u,v);
int ret = t[u].siz + 1;
root = merge(u,v);
return ret;
}
int kth(int u,int x){
int tmp = t[t[u].lc].siz + 1;
if(x == tmp)
return t[u].val;
if(x < tmp)
return kth(t[u].lc,x);
else
return kth(t[u].rc,x - tmp);
}
int pre(int x){
int u,v;
split(root,x - 1,u,v);
int ret = kth(u,t[u].siz);
root = merge(u,v);
return ret;
}
int nex(int x){
int u,v;
split(root,x,u,v);
int ret = kth(v,1);
root = merge(u,v);
return ret;
}
int main(){
srand(time(0));
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int q;
cin >> q;
while(q--){
int op,x;
cin >> op >> x;
if(op == 1)
insert(x);
if(op == 2)
remove(x);
if(op == 3)
cout << rnk(x) << '\n';
if(op == 4)
cout << kth(root,x) << '\n';
if(op == 5)
cout << pre(x) << '\n';
if(op == 6)
cout << nex(x) << '\n';
}
return 0;
}
例题 1:LOG
这里只讲平衡树的应用,略过了查询的分析过程。
经过分析(参考第一篇题解),本题回答能当且仅当:
- 所有数的和减大于
s 的数的和加上“大于s 的数的个数乘s ”。
这个问题非常好用 FHQ-Treap 解决。将原树分裂为两棵子树满足右子树包含所有大于
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 9;
int n,q;
int a[N];
struct node{
int val,sum,pri;
int lc,rc;
int siz;
} t[N];
int node_cnt,root;
void push_up(int u){
t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
t[u].sum = t[t[u].lc].sum + t[t[u].rc].sum + t[u].val;
}
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x,右子树所有节点权值 > x
if(u == 0){
L = R = 0;
return;
}
if(t[u].val <= x){
L = u;
split(t[u].rc,x,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
void new_node(int x){
t[++node_cnt] = (node){x,x,rand() * rand(),0,0,1};
}
void insert(int x){
int u,v;
split(root,x,u,v);
new_node(x);
int tmp = merge(u,node_cnt);
root = merge(tmp,v);
}
void remove(int x){
int u,v,w;
split(root,x,u,v);//分裂成 <= x 的子树和 > x 的子树
split(u,x - 1,u,w);//分裂成 < x 的子树和 == x 的子树
w = merge(t[w].lc,t[w].rc);//合并 w(== x 的子树) 的左右子树 ,相当于删除了一个 x
root = merge(merge(u,w),v);
}
int rnk(int x){
int u,v;
split(root,x - 1,u,v);
int ret = t[u].siz + 1;
merge(u,v);
return ret;
}
int kth(int u,int x){
int tmp = t[t[u].lc].siz + 1;
if(x == tmp)
return u;
if(x < tmp)
return kth(t[u].lc,x);
else
return kth(t[u].rc,x - tmp);
}
int query1(int x){//查询大于x的数的个数
int u,v;
split(root,x,u,v);
int ret = t[v].siz;
root = merge(u,v);
return ret;
}
int query2(int x){//查询大于x的数的和
int u,v;
split(root,x,u,v);
int ret = t[v].sum;
root = merge(u,v);
return ret;
}
signed main(){
srand(time(0));
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
while(q--){
string op;
cin >> op;
if(op == "U"){
int k,v;
cin >> k >> v;
remove(a[k]);
a[k] = v;
insert(a[k]);
}
else if(op == "Z"){
int c,s;
cin >> c >> s;
int tmp = t[root].sum - query2(s) + query1(s) * s;
cout << (tmp >= c * s ? "TAK" : "NIE") << '\n';
}
}
return 0;
}
【2】FHQ-Treap 维护序列
FHQ-Treap 和 Splay 一样,也是能维护序列的平衡树。
为什么平衡树能维护序列?这是因为两个等价的平衡树中序遍历是一样的,所以如果 BST 的关键字是下标的话,不管其怎么变,对应的序列都是一样的。
对于任何一个区间操作(假设为
不过不用像维护集合一样把下标存下来,比如在一个序列任意位置插入数时,分裂完后只要按照下标从小到大合并就没有问题(一个节点的下标肯定满足 FHQ-Treap 的性质)。
那么不把下标存起来,怎么分裂呢?
这就要用到一个序列下标是连续的这个性质了,因此,我们可以修改 split
,把它改成把一棵 FHQ-Treap 前
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成两棵子树满足左子树的大小为x
if(u == 0){
L = R = 0;
return;
}
push_down(u);
if(t[t[u].lc].siz < x){
L = u;
split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
FHQ-Treap 支持的操作很多样,接下来一个一个地看。
例题 1:文艺平衡树
区间翻转是一个基础的应用。方法如下:
-
将需要翻转的区间分裂出来
-
因为中序遍历代表整个序列,所以区间翻转相当于该子树所有节点都要交换左右子节点。这是极为低效的,考虑用懒标记优化。
-
最后把分裂出来的区间合并回去。
最后输出整个树的中序遍历。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n,m;
struct node{
int val,pri;
int lc,rc;
int siz;
int tag;
} t[N];
int node_cnt,root;
void push_up(int u){
t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}
void make_tag(int u){
t[u].tag ^= 1;
swap(t[u].lc,t[u].rc);
}
void push_down(int u){
if(t[u].tag){
make_tag(t[u].lc);
make_tag(t[u].rc);
t[u].tag = 0;
}
}
//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x
void split(int u,int x,int &L,int &R){
if(u == 0){
L = R = 0;
return;
}
push_down(u);
if(t[t[u].lc].siz < x){
L = u;
split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
push_down(u);
push_down(v);
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
void new_node(int x){
t[++node_cnt] = (node){x,rand() * rand(),0,0,1,0};
}
void reverse(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
make_tag(v);
root = merge(merge(u,v),w);
}
void print(int u){
if(!u)
return;
push_down(u);
print(t[u].lc);
cout << u << ' ';
print(t[u].rc);
}
int main(){
srand(time(0));
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++){
new_node(i);
root = merge(root,node_cnt);
}
while(m--){
int l,r;
cin >> l >> r;
reverse(l,r);
}
print(root);
return 0;
}
例题 2:文本编辑器
区间插入多个元素的话有两种实现方法:
-
一个一个元素插入,这在本题中可以通过,但不够高效。
-
把需要插入元素的 FHQ-Treap 以线性时间复杂度建出来,将原树从光标位置分裂开,依次合并左子树、新树和右子树。
区间删除就是把需要删除的区间分裂出来,然后直接合并两个不需要删除的区间。
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 4e6 + 9;
int n,m;
char a[N];
struct node{
char val;
int pri;
int lc,rc;
int siz;
} t[N];
int node_cnt,root;
void push_up(int u){
t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x,
if(u == 0){
L = R = 0;
return;
}
if(t[t[u].lc].siz < x){
L = u;
split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
int new_node(char x){
t[++node_cnt] = (node){
x,
rand() * rand(),
0,0,
1,
};
return node_cnt;
}
int build(int l,int r){
if(l == r)
return new_node(a[l]);
int u = merge(build(l,mid),build(mid + 1,r));
return u;
}
void Insert(int pos,int len){
int u,v;
split(root,pos,u,v);
int top = 0;
for(int i = 1;i <= len;i++){
char c = getchar();
while(c < 32 || c > 126)
c = getchar();
a[++top] = c;
}
root = merge(merge(u,build(1,top)),v);
}
void Delete(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
root = merge(u,w);
}
void Print(int u){
if(!u)
return;
Print(t[u].lc);
cout << t[u].val;
Print(t[u].rc);
}
void print(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
Print(v);
cout << '\n';
root = merge(merge(u,v),w);
}
signed main(){
srand(time(0));
cin >> m;
int pos = 0;
while(m--){
string op;
int len;
cin >> op;
if(op == "Move")
cin >> pos;
else if(op == "Insert"){
cin >> len;
Insert(pos,len);
}
else if(op == "Delete"){
cin >> len;
Delete(pos + 1,pos + len);
}
else if(op == "Get"){
cin >> len;
print(pos + 1,pos + len);
}
else if(op == "Prev")
pos--;
else if(op == "Next")
pos++;
}
return 0;
}
例题 3:维护序列
本题中还要维护区间信息/区间推平,实现方法和线段树一样,但是在 push_up
的时候不要漏了当前节点的值!这个和线段树不一样!!!
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 4e6 + 9,INF = 0x3f3f3f;
int n,m;
int a[N];
struct node{
int val;
int sum,Max,lsum,rsum;
int pri;
int lc,rc;
int siz;
int rev_tag,mod_tag;
} t[N];
int node_cnt,root;
void push_up(int u){
t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
t[u].sum = t[t[u].lc].sum + t[t[u].rc].sum + t[u].val;//不要漏了t[u].val!!!
t[u].Max = max(t[u].val + t[t[u].lc].rsum + t[t[u].rc].lsum,t[u].val);
if(t[u].lc)
t[u].Max = max(t[u].Max,t[t[u].lc].Max);
if(t[u].rc)
t[u].Max = max(t[u].Max,t[t[u].rc].Max);
//不要漏了t[u].val!!!
t[u].lsum = max(max(t[t[u].lc].lsum,t[t[u].lc].sum + t[u].val + t[t[u].rc].lsum),0);
t[u].rsum = max(max(t[t[u].rc].rsum,t[t[u].rc].sum + t[u].val + t[t[u].lc].rsum),0);
}
void make_rev_tag(int u){
t[u].rev_tag ^= 1;
swap(t[u].lc,t[u].rc);
swap(t[u].lsum,t[u].rsum);
}
void make_mod_tag(int u,int v){
t[u].val = t[u].mod_tag = v;
t[u].sum = v * t[u].siz;
t[u].Max = max(v,t[u].sum);
t[u].lsum = t[u].rsum = max(t[u].sum,0);
}
void push_down(int u){
if(t[u].rev_tag){
make_rev_tag(t[u].lc);
make_rev_tag(t[u].rc);
t[u].rev_tag = 0;
}
if(t[u].mod_tag != -INF){
make_mod_tag(t[u].lc,t[u].mod_tag);
make_mod_tag(t[u].rc,t[u].mod_tag);
t[u].mod_tag = -INF;
}
}
void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x,
if(u == 0){
L = R = 0;
return;
}
push_down(u);
if(t[t[u].lc].siz < x){
L = u;
split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
}
else{
R = u;
split(t[u].lc,x,L,t[u].lc);
}
push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根
return u | v;
push_down(u);
push_down(v);
if(t[u].pri > t[v].pri){//u优先级大于v优先级,则u应为v的父亲(大根堆性质)
t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val,所以合并t[u].rc和v
push_up(u);
return u;
}
else{//否则v应为u的父亲
t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val,所以合并u和t[v].lc
push_up(v);
return v;
}
}
int new_node(int x){
t[++node_cnt] = (node){
x,
x,x,max(x,0),max(x,0),
rand() * rand(),
0,0,
1,
0,-INF
};
return node_cnt;
}
int build(int l,int r){
if(l == r)
return new_node(a[l]);
int u = merge(build(l,mid),build(mid + 1,r));
//push_up(u);
return u;
}
void Insert(int pos,int tot){
int u,v;
split(root,pos,u,v);
for(int i = 1;i <= tot;i++)
cin >> a[i];
root = merge(merge(u,build(1,tot)),v);
}
void Delete(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
root = merge(u,w);
}
void Modify(int l,int r,int k){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
make_mod_tag(v,k);
root = merge(merge(u,v),w);
}
void Reverse(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
make_rev_tag(v);
root = merge(merge(u,v),w);
}
int query_sum(int l,int r){
int u,v,w;
split(root,r,u,w);
split(u,l - 1,u,v);
int ret = t[v].sum;
root = merge(merge(u,v),w);
return ret;
}
signed main(){
srand(time(0));
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
root = merge(root,build(1,n));
while(m--){
string op;
int pos,tot;
cin >> op;
if(op == "INSERT"){
cin >> pos >> tot;
Insert(pos,tot);
}
else if(op == "DELETE"){
cin >> pos >> tot;
Delete(pos,pos + tot - 1);
}
else if(op == "MAKE-SAME"){
int v;
cin >> pos >> tot >> v;
Modify(pos,pos + tot - 1,v);
}
else if(op == "REVERSE"){
cin >> pos >> tot;
Reverse(pos,pos + tot - 1);
}
else if(op == "GET-SUM"){
cin >> pos >> tot;
cout << query_sum(pos,pos + tot - 1) << '\n';
}
else if(op == "MAX-SUM")
cout << t[root].Max << '\n';
}
return 0;
}
例题 4:SuperMemo
其实和上面一题没什么区别,REVOLVE
操作也不难实现。见题解。