非旋TREAP

非旋TREAP
- 一、TREAP—新的树形结构
- 二、课后习题以及一些思路

一、TREAP—新的树形结构

1.treap=tree+heap

首先可以知道的是，他作为一个树形结构，很多操作都可以达到logn的强度，这是tree的来源

其次，treap实际上（个人觉得）很像一个二叉搜索树，换句话说，我们建立这颗数时要有一个值，（假设这个值叫做key吧），那么要满足一个点左子树内的点的key都小于它，右子树内的点的key都大于它。

最后，我们还可以人为安排一个值（这里称为rank),在建立树的时候可以去满足任何一棵子树必须是rank值最小的点作为根。

2.更优秀的时间复杂度

我们知道搜索树的时间复杂度和这个树的高度(n)成正比，为了尽力压缩这个高度，我们可以给rand值赋值为随机值

注意：这样做的话，treap会失去一个安排最小值的功能，交换了时间复杂度的更优秀

这是什意思呢，看这道题，：[P3165 CQOI2014]排序机械臂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于我要寻找这个无序序列中的最小值，我的rand不能随机而是要赋值为输入的val，这样可以保证最小的val 在根节点处，但也因此时间复杂度会大大增加。

不理解？没事，先往下看，慢慢来。

3.treap的基础打法

为了更好地记忆，我认为最基础的应该分为一下几个函数来记忆

1.基本框架-开数组

struct node{
	int val;//值
	int sz;//大小
	int ls;//左儿子
	int rs;//右儿子
	int rk;//保证根节点的值，上面讲到过
}tree[200005];

记住了，五个基本的量（sz的应用很多，所以尽量要打上）

还有，一定要清楚地辨析key和val ,这两个是不一定等的（但是一般key就是val,按val 大小建树）

2.动态开点

int newnode(int v){
    tree[++st].sz=1;
    tree[st].val=v;
    tree[st].rk=rand();
    return st;
}

代码的意思是，建立一个代号为st,st的val 为v的点

为了节约时间复杂度，利用随机化函数rand()来给rk;

注意：rand不能作为数组的名字，会G掉，但DEV c++查不出来

注意：后面会讲到有关pushdown的东西，一定要注意初始化，总之就是除了rs,ls,其他的都尽量在这里给初始值，不然都不知道错在哪里

3.sz的维护

void pushup(int root){
	int l=tree[root].ls;
	int r=tree[root].rs;
	tree[root].sz=tree[r].sz+tree[l].sz+1;
	return ;
}

很容易，类比线段树pushup

4.分离和统一

死记硬背就好，顺序不能写错。

split用于拆分一颗树，返回拆成两个数的根（&x，&y)

merge则是合并两个树，返回合成的新根

当然了，这里的split是按sz的大小来分的(分裂为刚好siz=k的子树和剩下的子树），还可以按照val的大小来分

注意：如果要按照val分的话，我树的key必须就是val,否则的话val是无序的不能分

注意，按照val分裂是小于等于，按照sz分裂的话就是小于，但merge都一样

注意：使用merge时都要root=merge(r1,r2),千万别漏了root=这个东西

！！！注意！！！，我merge(a,b)时，a的key必须小于b的key

按照sz来分裂

int merge(int x,int y){
	if(x==0){
		return y;
	}
	if(y==0){
		return x;
	}
	if(tree[x].rk<tree[y].rk){
		pushdown(x);
		tree[x].rs=merge(tree[x].rs,y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		tree[y].ls=merge(x,tree[y].ls);
		pushup(y);
		return y;
	}
}
void split(int rt,int k,int &x,int &y)
{
    if(rt==0){
        x=y=0;
        return;
    }
    pushdown(rt);
    if(tree[tree[rt].ls].sz<k){
    	x=rt;
		split(tree[rt].rs,k-tree[tree[rt].ls].sz-1,tree[rt].rs,y);
	}
    else{
        y=rt;
		split(tree[rt].ls,k,x,tree[rt].ls);	
	}    
    pushup(rt);
}

按照val来分裂的：

void split(int root,int k,int &x,int &y){
    if(root==0){
    	x=0;	
    	y=0;
	} 
    else{
        if(val[root]<=k){
        	x=root;
			split(son[root][1],k,son[root][1],y);
		}
        else{
        	y=root;
			split(son[root][0],k,x,son[root][0]);
		}
        pushup(root);
    }
}

4.treap的进阶使用

1.treap相比于线段树的好处

为什么要用treap呢，这也关系到进阶使用的一些理解问题

1.好理解，好拆分，好合并，随意加点

2.相比线段树而言，它支持区间翻转，而线段树就很难受（12345翻转2-3得14325)，下一个（2）中我会说明

2.在treap上pushup和pushdown

1.总体规则

pushdown和pushup有一个总体规则:

1.在自己做了标记的事后下传标记，但儿子不做。

什么意思？例如我当前节点为x,它的儿子设为ls,rs.如果我现在x的翻转标记为1（要翻转），那么我就swap（ls,rs),然后下传lz至ls和rs,但不继续往下做了

2.位置在断/合并前后

什么意思，我的pushup在split中可以看到还没开始断开就down了

if(rt==0){
        x=y=0;
        return;
    }
    pushdown(rt);
......

在merge中,也是在没有merge前down了

int merge(int x,int y){
	if(x==0){
		return y;
	}
	if(y==0){
		return x;
	}
	if(tree[x].rk<tree[y].rk){
		pushdown(x);
		tree[x].rs=merge(tree[x].rs,y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		tree[y].ls=merge(x,tree[y].ls);
		pushup(y);
		return y;
	}
}

至于pushup，位置不用修改，直接在维护sz的pushup中维护就行了

注意：个人觉得，为了思路清晰，最好多写几个函数

代码（pushdown)

void pushdown(int rt){
	if(tree[rt].lz==1){
		swap(tree[rt].ls,tree[rt].rs);
		if(tree[rt].ls){
			change(tree[rt].ls);
		}
		if(tree[rt].rs){
			change(tree[rt].rs);
		}
		tree[rt].lz=0;
	}
}

个人觉得，后面很多题都有很多的lz,很多种操作，因此，可以吧swap那里单独拿出来写个函数

比如，我要是又有个某个区间整体赋为某个值得lzval,我就多写个if(lzval!=-1)cover(ls),cover(rs);思路清晰一些