简介
\(fhq\_treap\)是一种非旋平衡树。在学习这篇文章之前，还是先学习一下普通\(treap\)吧
优点
相比于普通的\(treap\)，它可以处理区间操作。
相比于\(splay\)，它简洁易懂，代码也较短。
缺点
要比\(splay\)和\(treap\)慢
基础操作
\(fhq\_treap\)最基本的两个操作就是分裂和合并。
分裂
即把一个\(treap\)分为两个。有按照权值分和按照大小分两种方式。
具体方法:
比着代码划拉划拉就知道了(懒)。
按权值分
void split(int rt,int val,int &x,int &y) {
if(!rt) {
x = y = 0;
return;
}
if(TR[rt].w <= val) {
x = rt;split(rs,val,rs,y);
}
else {
y = rt;split(ls,val,x,ls);
}
update(rt);
}
按大小分
void split(int rt,int K,int &x,int &y) {
if(!rt) {
x = y = 0;return;
}
down(rt);
if(K <= TR[ls].siz) {
y = rt;split(ls,K,x,ls);
}
else {
x = rt;split(rs,K - TR[ls].siz - 1,rs,y);
}
update(rt);
}
合并
即把两个\(treap\)合并为一个。
注意要让id形成一个堆，且合并的两个树满足其中一个中的权值全部小于另一个。
具体方法:
比较简单，参考代码吧。。
int merge(int x,int y) {
if(!x || !y) return x + y;
if(TR[x].id < TR[y].id) {
TR[x].son[1] = merge(TR[x].son[1],y);
update(x);
return x;
}
TR[y].son[0] = merge(x,TR[y].son[0]);
update(y);
return y;
}
其他操作
插入
插入一个权值为\(x\)的数。
只需要将原来的\(treap\)按权值\(x\)分为\(L,R\)两棵树。
然后把\(x\)节点当成一个\(treap\)与\(L\)合并起来。然后再整体和\(R\)合并起来。
void insert(int x) {
int L,R;
split(root,x,L,R);
root = merge(merge(L,new_node(x)),R);
}
删除
删除一个权值为\(x\)的数。
将原来的\(treap\)按权值\(x\)分为\(L,R\)两棵子树。再按权值\(x-1\)将\(L\)分为\(L,rt\)两棵子树。
这时\(rt\)中就全都是权值为x的点了。删除根节点(也就是将根的两个孩子合并起来)。
操作完成别忘了合并回去。
void del(int x) {
int L,R,rt;
split(root,x,L,R);
split(L,x - 1,L,rt);
rt = merge(ls,rs);
root = merge(merge(L,rt),R);
}
查询排名
查询权值\(x\)的排名(定义为比\(x\)小的数的数量+1)。
将原\(treap\)按权值\(x-1\)分为\(L,R\)两棵子树。\(L\)的大小+1就是答案了。
操作完成别忘了合并回去。
int Rank(int x) {
int L,R;
split(root,x - 1,L,R);
int ret = TR[L].siz + 1;
root = merge(L,R);
return ret;
}
查询第k大
查询排名为\(k\)的数字。
如果排名小于等于左子树大小就查询左子树。
如果排名大于左子树大小+1就查询右子树，并且\(k-=\)左子树大小
否则返回当前节点。
int kth(int rt,int x) {
while(1) {
if(x == TR[ls].siz + 1) return rt;
if(x <= TR[ls].siz) rt = ls;
else {
x -= TR[ls].siz + 1;
rt = rs;
}
}
}
前驱
查询比\(x\)小的数中最大的数。
按权值\(x-1\)将原\(treap\)分为\(L,R\)两棵子树。
\(L\)子树中最大的那个就是答案。
操作完成别忘了合并回去。
int pre(int x) {
int L,R;
split(root,x - 1,L,R);
int ret = kth(L,TR[L].siz);
root = merge(L,R);return ret;
}
后继
查询比\(x\)大的数中最小的数。
按权值\(x\)将原\(treap\)分为\(L,R\)两棵子树。
\(R\)子树中最小的就是答案。
操作完成别忘了合并回去。
int nxt(int x) {
int L,R;
split(root,x,L,R);
int ret = kth(R,1);
root = merge(L,R);return ret;
}
处理区间
对区间\(l,r\)进行处理。
先按大小\(r\)将原\(treap\)分为\(L,R\)两棵子树。
再按大小\(l-1\)将\(L\)分为\(L1,L2\)两棵子树。
\(L2\)子树就是要处理的区间了。
操作完成别忘了合并回去。
void reverse(int l,int r) {
int L,R,rt,tmp;
split(root,r + 1,L,R);
split(L,l,tmp,rt);
TR[rt].rev ^= 1;
root = marge(marge(tmp,rt),R);
}
例题
/*
* @Author: wxyww
* @Date: 2019-04-13 08:47:22
* @Last Modified time: 2019-04-13 11:24:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls TR[rt].son[0]
#define rs TR[rt].son[1]
const int N = 100000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int w,id,siz,son[2];
}TR[N];
int root,tot;
int new_node(int val) {
++tot;
TR[tot].w = val,TR[tot].id = rand(),TR[tot].siz = 1;
return tot;
}
void update(int rt) {
TR[rt].siz = TR[ls].siz + TR[rs].siz + 1;
}
int merge(int x,int y) {
if(!x || !y) return x + y;
if(TR[x].id < TR[y].id) {
TR[x].son[1] = merge(TR[x].son[1],y);
update(x);
return x;
}
TR[y].son[0] = merge(x,TR[y].son[0]);
update(y);
return y;
}
void split(int rt,int val,int &x,int &y) {
if(!rt) {
x = y = 0;
return;
}
if(TR[rt].w <= val) {
x = rt;split(rs,val,rs,y);
}
else {
y = rt;split(ls,val,x,ls);
}
update(rt);
}
void insert(int x) {
int L,R;
split(root,x,L,R);
root = merge(merge(L,new_node(x)),R);
}
void del(int x) {
int L,R,rt;
split(root,x,L,R);
split(L,x - 1,L,rt);
rt = merge(ls,rs);
root = merge(merge(L,rt),R);
}
int Rank(int x) {
int L,R;
split(root,x - 1,L,R);
int ret = TR[L].siz + 1;
root = merge(L,R);
return ret;
}
int kth(int rt,int x) {
while(1) {
if(x == TR[ls].siz + 1) return rt;
if(x <= TR[ls].siz) rt = ls;
else {
x -= TR[ls].siz + 1;
rt = rs;
}
}
}
int pre(int x) {
int L,R;
split(root,x - 1,L,R);
int ret = kth(L,TR[L].siz);
root = merge(L,R);return ret;
}
int nxt(int x) {
int L,R;
split(root,x,L,R);
int ret = kth(R,1);
root = merge(L,R);return ret;
}
int main() {
srand(time(0));
int n = read();
while(n--) {
int opt = read(),x = read();
if(opt == 1) insert(x);
else if(opt == 2) del(x);
else if(opt == 3) printf("%d\n",Rank(x));
else if(opt == 4) printf("%d\n",TR[kth(root,x)].w);
else if(opt == 5) printf("%d\n",TR[pre(x)].w);
else printf("%d\n",TR[nxt(x)].w);
}
return 0;
}
/*
* @Author: wxyww
* @Date: 2019-04-13 10:46:59
* @Last Modified time: 2019-04-13 11:24:56
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls TR[rt].son[0]
#define rs TR[rt].son[1]
const int N = 100000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int w,id,siz,rev,son[2];
}TR[N];
int tot;
int root,n,m;
void update(int rt) {
TR[rt].siz = TR[ls].siz + TR[rs].siz + 1;
}
void down(int rt) {
if(TR[rt].rev) {
TR[ls].rev ^= 1;
TR[rs].rev ^= 1;
swap(ls,rs);
TR[rt].rev ^= 1;
}
}
int new_node(int x) {
++tot;
TR[tot].id = rand();TR[tot].siz = 1;TR[tot].w = x;TR[tot].rev = 0;
return tot;
}
int marge(int x,int y) {
if(!x || !y) return x + y;
down(x),down(y);
if(TR[x].id < TR[y].id) {
TR[x].son[1] = marge(TR[x].son[1],y);
update(x);
return x;
}
else {
TR[y].son[0] = marge(x,TR[y].son[0]);
update(y);
return y;
}
}
void split(int rt,int K,int &x,int &y) {
if(!rt) {
x = y = 0;return;
}
down(rt);
if(K <= TR[ls].siz) {
y = rt;split(ls,K,x,ls);
}
else {
x = rt;split(rs,K - TR[ls].siz - 1,rs,y);
}
update(rt);
}
void reverse(int l,int r) {
int L,R,rt,tmp;
split(root,r + 1,L,R);
split(L,l,tmp,rt);
TR[rt].rev ^= 1;
root = marge(marge(tmp,rt),R);
}
int build(int l,int r) {
if(l > r) return 0;
int mid = (l + r) >> 1;
int rt = new_node(mid - 1);
ls = build(l,mid - 1);
rs = build(mid + 1,r);
update(rt);
return rt;
}
void print(int rt) {
if(!rt) return;
down(rt);
print(ls);
if(TR[rt].w >= 1 && TR[rt].w <= n) printf("%d ",TR[rt].w);
print(rs);
}
int main() {
n = read(),m = read();
root = build(1,n + 2);
while(m--) {
int l = read(),r = read();
reverse(l,r);
}
print(root);
return 0;
}