非旋转Treap详解
利用其他人其中考试的时间，终于学完了非旋转Treap,它与普通Treap的区别就是它不旋转废话。前置知识只有BST和可并堆。
BST看这个博客，解释的挺清楚的。https://www.cnblogs.com/jiangminghong/p/9999884.html
可并堆就是用很快的时间合并两个堆。如果裸上一个并查集的话就是nlog2n.这个复杂度我们是不能接受的。正常的可并堆是维护一棵左偏树，我们用一个参数dis[x]表示从x点出发能够向右走的最大步数。每次两个堆合并时，我们就把一个堆扔到另一个堆里就行了。
在旋转Treap中，我们用随机数来保持平衡树的平衡.非旋转Treap也是同样的做法。
1 int lson[N];//表示当前点的左儿子 2 int rson[N];//表示当前点的右儿子 3 int key[N];//表示当前点的随机数(保持平衡树的平衡) 4 int val[N];//表示当前点的权值 5 int size[N];//表示当前点子树的大小
这就是我们需要维护的信息。
看看操作吧
1.Merge【合并】O(logn)
2.Split【拆分】O(logn)
只有两个
可资瓷使用范围
1.Insert Newnode+Merge O(logn)
2.Delete Split+Split+Merge O(logn)
3.Find_kth Split+Split O(logn)
4.Query Split+Split O(logn)
5.各种区间操作
1.split
split操作就是以一个点为界限，将平衡树分裂成两棵平衡树，保证左边平衡树中任意点权值小于右边平衡树中任意点的权值。
以将平衡树分裂成权值<=val和权值>val两部分为例：从根节点开始往下查找，当当前点权值<=val时，将当前点及它的右子树接到分裂后第二棵平衡树的左子树上；反之则将当前点及它的左子树接到分裂后第一棵平衡树的右子树上，直到找到叶子节点为止。
void split(int now,int k,int &x,int &y)//now表示现在的位置，k表示要查询的权值，x,y分别为拆分后两子树的根
{
if(!now)
{
x=y=0;
return ;
}
if(val[now]<=k)
x=now,split(rson[now],k,rson[now],y);
else
y=now,split(lson[now],k,x,lson[now]);
push_up(now);
return ;
}
如果想要拆分成前K个点与后n-K个点也是同理的,判断的条件就是size喽！
void split(int now,int k,int &x,int &y) { if(!now) { x=y=0; return ; } if(size[lson[now]]<k) x=now,split(rson[now],k-size[lson[now]]-1,rson[now],y); else y=now,split(lson[now],k,x,lson[now]); push_up(now); }
2.merge
merge这个操作就是将两个堆合并，我们请出可并堆。可并堆的合并方式就是按照随机数大小来合并。
int merge(int x,int y) { if(!x||!y) return x|y; if(key[x]<key[y]) { rson[x]=merge(rson[x],y); push_up(x); return x; } else { lson[y]=merge(x,lson[y]); push_up(y) return y; } }
有木有一直好奇push_up函数啊，其实和线段树一样,维护子树的一些信息。
有了这两个sao操作，是不是就可以在序列上想干嘛就干嘛了？
1.Newnode
新建节点，加入平衡树
int newnode(int x) { size[++tot]=1; val[tot]=x; key[tot]=rand()*rand(); return tot; }
split(root,a,x,y);
root=merge(merge(x,newnode(a)),y);
2.Delete
划分成3个区间，之后合并
split(root,a,x,z); split(x,a-1,x,y); y=merge(lson[y],rson[y]); root=merge(merge(x,y),z);
3.Query(查询以x为根排名第K的数)
判断K和左子树大小的关系，根据size找到答案。
int kth(int now,int k) { while(1) { if(now==0) break; if(k<=size[lson[now]]) now=lson[now]; else if(k==size[lson[now]]) return now; else k-=size[lson[now]]+1,now=rson[now]; } return 0; }
4.前驱&后继
split(root,a-1,x,y); printf("%d\n",val[kth(x,size[x])]); root=merge(x,y); //前驱 split(root,a,x,y); printf("%d\n",val[kth(y,1)]); root=merge(x,y); //后继
LuoguP3369 普通平衡树
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 1000100 int tot; int size[N]; int lson[N]; int rson[N]; int key[N]; int val[N]; int n,m; int root; int x,y; void push_up(int x){size[x]=size[lson[x]]+size[rson[x]]+1;return ;} int newnode(int x) { size[++tot]=1; val[tot]=x; key[tot]=rand(); return tot; } int merge(int x,int y) { if(!x||!y) return x+y; if(key[x]<key[y]) { rson[x]=merge(rson[x],y); push_up(x); return x; } else { lson[y]=merge(x,lson[y]); push_up(y); return y; } } void split(int now,int k,int &x,int &y) { if(!now) x=y=0; else { if(val[now]<=k) x=now,split(rson[now],k,rson[now],y); else y=now,split(lson[now],k,x,lson[now]); push_up(now); } return ; } int kth(int now,int k) { while(1) { if(k<=size[lson[now]]) now=lson[now]; else if(k==size[lson[now]]+1) return now; else k-=size[lson[now]]+1,now=rson[now]; } return 0; } int main() { srand(20030305); scanf("%d",&n); int opt,a; while(n--) { scanf("%d%d",&opt,&a); if(opt==1) { split(root,a,x,y); root=merge(merge(x,newnode(a)),y); } if(opt==2) { int z; split(root,a,x,z); split(x,a-1,x,y); y=merge(lson[y],rson[y]); root=merge(merge(x,y),z); } if(opt==3) { split(root,a-1,x,y); printf("%d\n",size[x]+1); root=merge(x,y); } if(opt==4) printf("%d\n",val[kth(root,a)]); if(opt==5) { split(root,a-1,x,y); printf("%d\n",val[kth(x,size[x])]); root=merge(x,y); } if(opt==6) { split(root,a,x,y); printf("%d\n",val[kth(y,1)]); root=merge(x,y); } } return 0; }