fhq-treap

可持久化平衡树

P3835 【模板】可持久化平衡树

fhq-treap 的关键思想在于数的分裂和合并思想。

数组变量意义

struct po{
    int l,r; 
	int s_z;//子树大小 
	int i_d;//随即优先级 
	int v;//节点价值 
}t_r[o_o<<6];
int x_p;//节点编号 
int g_i[o_o];//根节点（主席树） 

动态开点，更新节点信息

常规操作。

void u_p(int k){//更新节点子树大小 
    t_r[k].s_z=t_r[t_r[k].l].s_z+t_r[t_r[k].r].s_z+1;
}
void n_d(int &k,int x){//动态开点 
	k=++x_p; 
    t_r[k].v=x;//初始化 
	t_r[k].s_z=1;
	t_r[k].i_d=rand();
}

插入

先将以这个值为界限，将整棵树分成两部分。平衡树的性质不难得出：平衡树分裂成两个树，平衡的特性不变（两棵树都是平衡树，相对位置 不变）。

例子：（符合平衡树特性）

     6
    / \
   /   \
  3     8
 / \   / \
1   5 7   9

现在要插入 $4$，不断分裂目标值在节点和树的子树的范围内的树的左右子树。

分裂后：

   |  6
   | / \
   |5   \
  3|     8
 / |    / \
1  |   7   9

这时非常明显，可以将 $4$ 并入其中一棵树的节点，但为了保持树的“平衡”，要按照随机的优先级决定是作为子节点还是父节点（对于左子树而言）。

插入后：（插到左边的树中）

      6
     / \
    5   \
  3      8
 / \    / \
1   4  7   9

或（优先级随机，相对位置 不能变，但 相对高度 可以改变）。

        6
    4  / \
   /  5   \
  3        8
 /        / \
1        7   9

合并后：

（第一种情况）

      6
     / \
    /   \
   /     \
  3       8
 / \     / \
1   4   7   9
     \
      5

或

      6
     / \
    /   \
   /     \
  3       8
 / \     / \
1   5   7   9
   /  
  4  

（第二种情况）

       6
      / \
     4   \
    / \   \
   /   5   \
  3         8
 /         / \
1         7   9

或

        6
       / \
      5   \
     /     \
    4       \
   /         \
  3           8
 /           / \
1           7   9

（随机性可以尽量使最后的树平衡，很小几率会退化成链）

void a_d(int &k,int v){//加点 
    int x=0,y=0,z=0;
    f_l(k,v,x,y);//k 为根的子树，以 v 为界限分裂树 
    n_d(z,v);//开新点 
    k=h_b(h_b(x,z),y);//合并完整原来的树（将树在合并回去），新根节点为 k 
}

在调用分裂（当前数会分到左子树中，和写法有关，关键在于与当前值比较是判断分裂时的等号）和合并函数时思路会异常的清晰。

int h_b(int l,int r){//合并 
    if(!l||!r)return l+r;//节点子树不全 
    if(t_r[l].i_d>t_r[r].i_d){//随机权更大 
        int n_n=++x_p;//新节点编号 
		t_r[n_n]=t_r[l];//继承原节点信息 
        t_r[n_n].r=h_b(t_r[n_n].r,r);//接右子树 
        u_p(n_n);//更新节点信息 
		return n_n;//返回节点序号 
    }else{
        int n_n=++x_p;//新节点编号 
		t_r[n_n]=t_r[r];//继承原节点信息 
        t_r[n_n].l=h_b(l,t_r[n_n].l);//接左子树 
        u_p(n_n);//更新节点信息 
		return n_n;//返回节点序号 
    }
}
void f_l(int k,int v,int &l,int &r){//分裂 
    if(!k)l=r=0;//当前节点不存在 
    else{
        if(t_r[k].v<=v){//目标值比当前值大（当前值会分到左子树） 
            l=++x_p;//新节点 
			t_r[l]=t_r[k];//赋值节点信息 
            f_l(t_r[l].r,v,t_r[l].r,r);//在右子树中找 
            u_p(l);//更新节点信息 
        }else {
            r=++x_p;//新节点（含有当前值） 
			t_r[r]=t_r[k];//赋值节点信息 
            f_l(t_r[r].l,v,l,t_r[r].l);//在左子树中找 
            u_p(r);//更新节点信息 
        }
    }
}

删点

先将整棵树按 $v$ 的值分成两棵树。再将左边的树根据 $v-1$ 分成两棵树。这样此时有左，中，右三棵子树。而中间的树以 $v$ 为更节点，此时直接讲它的左右子树合并成新的子树，$v$ 节点就相当于被删了。

void d_l(int &k,int v){//删点 
    int x=0,y=0,z=0;
    f_l(k,v,x,z);//k 为根的子树，以 v 为界限分裂为 x，z 根节点子树 
    f_l(x,v-1,x,y);//x 为根的子树，以 v-1 为界限分裂 x，y 根节点的子树 
    //价值为 v 的点被“孤立”了 （自成一棵树，只有一个节点，其本身） 
    y=h_b(t_r[y].l,t_r[y].r);//合并 v 节点的子树，新根复制到 y 节点中 
    k=h_b(h_b(x,y),z);//合并完整原来的树（将树在合并回去），新根节点为 k  
}

找的排名（数的排名）

维护了每个点的值大小，通过比对当前值与目标值大小关系，找到排名的位置（左子树，右子树或当前节点），递归寻找即可。

正常的分裂合并操作。

int f_p(int &k,int v){//找 x 的排名 
    int x,y;
    f_l(k,v-1,x,y);//以 v-1 为界线，分裂为 x，y 根节点子树 
    int a_s=t_r[x].s_z+1;//左子树大小 +1 
    k=h_b(x,y);//将树合并回去，更节点仍是 k 
    return a_s;//返回结果 
}

找数（排名的数）

维护了每个点的子树大小，可以通过左子树的大小可以判断找的排名的位置（左子树，右子树或当前节点），递归寻找即可。

正常的分裂合并操作。

int f_x(int k,int v){//排名为 x 的数 
    if(v==t_r[t_r[k].l].s_z+1)return t_r[k].v;//左子树大小 +1 是目标排名，直接返回值 
    else if(v<=t_r[t_r[k].l].s_z)return f_x(t_r[k].l,v);//目标值小，被包含在左子树中 
    else return f_x(t_r[k].r,v-t_r[t_r[k].l].s_z-1);//在右子树中找 
}

前驱

先将树按 $v-1$ 分为左右两棵树，在左子树中一找排名最大的即为前驱。

int f_q(int &k,int v){//找前驱 
    int x,y,n_n,a_s;
    f_l(k,v-1,x,y);//k 为根的子树，以 v-1 为界限分裂为 x，y 根节点子树 
    if(!x)return -2147483647;//未找到子节点，返回题目要求值 
    n_n=t_r[x].s_z;
    a_s=f_x(x,n_n);//每回找右子树（越靠右值越大，越接近正确答案） 
    k=h_b(x,y);//拆的输在合并回去 
    return a_s;//返回结果 
}

后继

先将树按 $v$ 分为左右两棵树，在右子树中一找排名第一的即为后继。

int f_h(int &k,int v){//找后继 
    int x,y,a_s;
    f_l(k,v,x,y);//k 为根的子树，以 v 为界限分裂为 x，y 根节点子树 
    if(!y)return 2147483647;//未找到子节点，返回题目要求值 
    a_s=f_x(y,1);//找右子树中排名第一的 
    k=h_b(x,y);//拆的输在合并回去 
    return a_s;//返回结果 
}

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<cctype>
#include<ctime>
using namespace std;
long long r_r(){//快读 
	long long k=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar(); 
	}
	return k*f;
}
const int o_o=1e6+10;//数组下标大小 
struct po{
    int l,r; 
	int s_z;//子树大小 
	int i_d;//随即优先级 
	int v;//节点价值 
}t_r[o_o<<6];
int x_p;//节点编号 
int g_i[o_o];//根节点（主席树） 
void u_p(int k){//更新节点子树大小 
    t_r[k].s_z=t_r[t_r[k].l].s_z+t_r[t_r[k].r].s_z+1;
}
void n_d(int &k,int x){//动态开点 
	k=++x_p; 
    t_r[k].v=x;//初始化 
	t_r[k].s_z=1;
	t_r[k].i_d=rand();
}
int h_b(int l,int r){//合并 
    if(!l||!r)return l+r;//节点子树不全 
    if(t_r[l].i_d>t_r[r].i_d){//随机权更大 
        int n_n=++x_p;//新节点编号 
		t_r[n_n]=t_r[l];//继承原节点信息 
        t_r[n_n].r=h_b(t_r[n_n].r,r);//接右子树 
        u_p(n_n);//更新节点信息 
		return n_n;//返回节点序号 
    }else{
        int n_n=++x_p;//新节点编号 
		t_r[n_n]=t_r[r];//继承原节点信息 
        t_r[n_n].l=h_b(l,t_r[n_n].l);//接左子树 
        u_p(n_n);//更新节点信息 
		return n_n;//返回节点序号 
    }
}
void f_l(int k,int v,int &l,int &r){//分裂 
    if(!k)l=r=0;//当前节点不存在 
    else{
        if(t_r[k].v<=v){//目标值比当前值大 
            l=++x_p;//新节点 
			t_r[l]=t_r[k];//赋值节点信息 
            f_l(t_r[l].r,v,t_r[l].r,r);//在右子树中找 
            u_p(l);//更新节点信息 
        }else {
            r=++x_p;//新节点 
			t_r[r]=t_r[k];//赋值节点信息 
            f_l(t_r[r].l,v,l,t_r[r].l);//在左子树中找 
            u_p(r);//更新节点信息 
        }
    }
}
void a_d(int &k,int v){//加点 
    int x=0,y=0,z=0;
    f_l(k,v,x,y);//k 为根的子树，以 v 为界限分裂树 
    n_d(z,v);//开新点 
    k=h_b(h_b(x,z),y);//合并完整原来的树（将树在合并回去），新根节点为 k 
}
void d_l(int &k,int v){//删点 
    int x=0,y=0,z=0;
    f_l(k,v,x,z);//k 为根的子树，以 v 为界限分裂为 x，z 根节点子树 
    f_l(x,v-1,x,y);//x 为根的子树，以 v-1 为界限分裂 x，y 根节点的子树 
    //价值为 v 的点被“孤立”了 （自成一棵树，只有一个节点，其本身） 
    y=h_b(t_r[y].l,t_r[y].r);//合并 v 节点的子树，新根复制到 y 节点中 
    k=h_b(h_b(x,y),z);//合并完整原来的树（将树在合并回去），新根节点为 k  
}
int f_p(int &k,int v){//找 x 的排名 
    int x,y;
    f_l(k,v-1,x,y);//以 v-1 为界线，分裂为 x，y 根节点子树 
    int a_s=t_r[x].s_z+1;//左子树大小 +1 
    k=h_b(x,y);//将树合并回去，更节点仍是 k 
    return a_s;//返回结果 
}
int f_x(int k,int v){//排名为 x 的数 
    if(v==t_r[t_r[k].l].s_z+1)return t_r[k].v;//左子树大小 +1 是目标排名，直接返回值 
    else if(v<=t_r[t_r[k].l].s_z)return f_x(t_r[k].l,v);//目标值小，被包含在左子树中 
    else return f_x(t_r[k].r,v-t_r[t_r[k].l].s_z-1);//在右子树中找 
}
int f_q(int &k,int v){//找前驱 
    int x,y,n_n,a_s;
    f_l(k,v-1,x,y);//k 为根的子树，以 v-1 为界限分裂为 x，y 根节点子树 
    if(!x)return -2147483647;//未找到子节点，返回题目要求值 
    n_n=t_r[x].s_z;
    a_s=f_x(x,n_n);//找左子树中排名最大的 
    k=h_b(x,y);//拆的输在合并回去 
    return a_s;//返回结果 
}
int f_h(int &k,int v){//找后继 
    int x,y,a_s;
    f_l(k,v,x,y);//k 为根的子树，以 v 为界限分裂为 x，y 根节点子树 
    if(!y)return 2147483647;//未找到子节点，返回题目要求值 
    a_s=f_x(y,1);//找右子树中排名第一的 
    k=h_b(x,y);//拆的输在合并回去 
    return a_s;//返回结果 
}
int main(){
    int n=r_r();
    for(int i=1;i<=n;++i){
        int l_s=r_r(),op=r_r(),v=r_r();
        g_i[i]=g_i[l_s];//复制历史版本信息 
        if(op==1)a_d(g_i[i],v);//加点 
        else if(op==2)d_l(g_i[i],v);//删点 
        else if(op==3)printf("%d\n",f_p(g_i[i],v));//查找 x 的排名 
        else if(op==4)printf("%d\n",f_x(g_i[i],v));//查找排名为 x 的数 
        else if(op==5)printf("%d\n",f_q(g_i[i],v));//前驱 
        else printf("%d\n",f_h(g_i[i],v));//后继 
    }
    return 0;
}