平衡树（基础）

普通平衡树

P3369 【模板】普通平衡树

旋转原理

为方便理解，先定义两个名词：

• 相对位置：树被压缩成一维数组后，节点的左右位置关系。

• 相对高度：相邻的两个节点在树上的高低关系。

由于平衡树的性质：左节点比父节点的值小，父节点的值比父节点的值大。所以我们将整棵树压成一维数组后，变成了一个升序数组。

数            (5)
              /|\
             / | \
            /  |  \
           /   |   \
          /    |    \
        (3)    |    (7)
        /|\    |    /|\
       / | \   |   / | \
     (1) | (4) | (6) | (9)
      |  |  |  |  |  |  |
数组 (1)(3)(4)(5)(6)(7)(9)

平衡树的建立会根据数据的插入决定。例如不同顺序插入 $1,3,4,5,6,7,9$。

按 $5,3,7,1,4,6,9$ 的顺序插入：

数            (5)
              /|\
             / | \
            /  |  \
           /   |   \
          /    |    \
        (3)    |    (7)
        /|\    |    /|\
       / | \   |   / | \
     (1) | (4) | (6) | (9)
      |  |  |  |  |  |  |
数组 (1)(3)(4)(5)(6)(7)(9)

按 $1,3,4,5,6,7,9$ 的顺序插入：

数   (1)
      | \
      | (3)
      |  | \
      |  | (4)
      |  |  | \
      |  |  | (5)
      |  |  |  | \
      |  |  |  | (6)
      |  |  |  |  | \
      |  |  |  |  | (7)
      |  |  |  |  |  | \
      |  |  |  |  |  | (9)
      |  |  |  |  |  |  |
数组 (1)(3)(4)(5)(6)(7)(9)

退化的惨不忍睹。

我们旋转的目的，是将整棵树尽量向着满二叉树进步，查询一次或插入一个数，便利的次数直接影响时间效率。而越接近满二叉树，时间复杂路越接近
$O(\log_n)$ 而如果退化成一条链，时间复杂度变为 $O(n)$。为了防止这种情况的出现，便有了旋转操作。

旋转操作并不会破坏平衡树的性质，只是改变值在树上的相对高度。上面的两个图可以发现顺序相同，但值在两个图中的相对高度不同，而旋转操作可以理解成将第二个图向着第一个图的方向转换（一些节点的相对高度下拉或上提）。

旋转过程

数   (1)
      | \
      | (3)
      |  | \
      |  | (4)
      |  |  | \
      |  |  | (5)
      |  |  |  | \
      |  |  |  | (6)
      |  |  |  |  | \
      |  |  |  |  | (7)
      |  |  |  |  |  | \
      |  |  |  |  |  | (9)
      |  |  |  |  |  |  |
数组 (1)(3)(4)(5)(6)(7)(9)

以 $5$ 为旋转节点旋转。为了让他更接近满二叉树我们要左旋，即：让他的父亲变为它的左儿子（父节点相对位置下拉）。

数   (1)
      | \
      | (3)
      |  | \
      |  |  \
      |  |   \
      |  |    \
      |  |    (5)
      |  |   / | \
      |  | (4) | (6)
      |  |  |  |  | \
      |  |  |  |  | (7)
      |  |  |  |  |  | \
      |  |  |  |  |  | (9)
      |  |  |  |  |  |  |
数组 (1)(3)(4)(5)(6)(7)(9)

注意：平衡树的左右旋转的操作可以抵消，就是说以一个点左旋后，在以这个点右旋会变为原来的样子。（上一个图以 $5$ 节点右旋换变成左旋的图）。

上面的图可能不方便理解，我们演示一个旋转后是满二叉树的例子。

            (1)
            /|\
           / | \
          /  |  \
         /   |   \
        /    |    \
      (2)    |   (3)
      /|\    |    |
     / | \   |    |
    /  |  \  |    |  
  (4)  | (5) |    |
  /|\  |  |  |    |
(6)|(7)|  |  |    |

以 $2$ 节点右旋即可成为满二叉树，我们顺便演示一下旋转的过程。

首先我们要知道旋转后的样子（没有目地的旋转是无用功）。

        (2) 
        /|\
       / | \
      /  |  \
     /   |   \
   (4)   |   (1)
   /|\   |   /|\
  / | \  |  / | \
(6) | (7)|(5) | (3)

（不难看出，两个节点的左右关系没变，变的只是相对高度，它的原理其实就是平衡术的性质：左儿子 $ < $ 父节点 $ < $ 右儿子）

相对位置不变，我们又要右旋 $2$ 节点，所以 $1$ 要成为 $2$ 的儿子，$1$ 比 $2$ 大所以会成为 $2$ 的右儿子，但是 $2$ 本身有右儿子 $5$，所以 $1$ 和 $5$ 也要有新的关系，因为 $1$ 在 $5$ 的右边（相对位置）所以 $5$ 只能是 $1$ 的左儿子。

大概的方向也有了，可以旋转了。首先建一个新节点来保存 $2$ 的右节点，这样就可以为 $1$ 节点腾出位置，$1$ 节点可以直接成为 $2$ 的右子树，然后将 $2$ 原来的右节点接到 $1$ 的左子树，最后换根,将更的编号直接换成 $2$，更新节点信息即可。要先更新节点信息，才能保证根节点是最新信息。

但是，由于我们平衡树只存子节点，存父节点不必要的，所以我们还要讨论节点的左右旋（道理极其相似）。我们现在站在父节点的角度来看这次旋转。

            (1)
            /|\
           / | \
          /  |  \
         /   |   \
        /    |    \
      (2)    |   (3)
      /|\    |    |
     / | \   |    |
    /  |  \  |    |  
  (4)  | (5) |    |
  /|\  |  |  |    |
(6)|(7)|  |  |    |

我们现在以 $1$ 的角度看这次旋转。旋转的方向不变，还是向右。但是表达不同（思路一样，为方便理解才有了前面的节点 $2$ 的视角）。

先定义一个新变量保存 $1$ 的左儿子 $2$ 节点，然后将 $2$ 的右儿子接到 $1$ 的左子树（相对位置不变），接着再将 $1$ 接到 $2$ 的右子树，换根根变成 $2$ 节点，旋转完成。先更新子节点 $1$ 的子树大小，在更新新根 $2$ 的子树大小。

void b_l(int &k){//左旋 
	int k_k=t_r[k].r;//存当前节点的右节点 
	t_r[k].r=t_r[k_k].l;//右节点的左子树接到当前节点的右边 
	t_r[k_k].l=k;//当前节点接到右节点的左边 
	k=k_k;//右节点取代当前节点（换根） 
	u_p(t_r[k].l);//更新新的根的左子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}
void b_r(int &k){//右旋 
	int k_k=t_r[k].l;//存当前节点的左节点 
	t_r[k].l=t_r[k_k].r;//左节点的右子树接到当前节点的左边 
	t_r[k_k].r=k;//当前节点接到做节点的右边 
	k=k_k;//左节点取代当前节点（换根） 
	u_p(t_r[k].r);//更新新的根的右子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#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,m_x=1e9+10;
struct po{
	int v;//节点价值 
	int l,r;//左右儿子 
	int s_z;//节点大小 
	int n;//相同节点数量
	int i_d;//随机优先值 
}t_r[o_o];
int x_p;//新节点编号 
int g_g;//根节点 
mt19937 m_t(time(0));//随机数种子 
int n_w(int v){//动态开点 
	t_r[++x_p].v=v;//新节点的值 
	t_r[x_p].i_d=m_t()%(o_o<<1);//获取随机优先级 
	t_r[x_p].s_z=1;//初始化大小 
	t_r[x_p].n=1;//初始化相同节点数量 
	return x_p;//返回新节点编号（方便父节点存左右儿子） 
}
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+t_r[k].n;//节点子树大小是左右子树的和加上相同节点个数 
}
void b_t(){
	g_g=n_w(-m_x),t_r[g_g].r=n_w(m_x);//初始化平衡树，放最大最小值 
	u_p(g_g);//更新节点子树信息 
}
void b_l(int &k){//左旋 
	int k_k=t_r[k].r;//存当前节点的右节点 
	t_r[k].r=t_r[k_k].l;//右节点的左子树接到当前节点的右边 
	t_r[k_k].l=k;//当前节点接到右节点的左边 
	k=k_k;//右节点取代当前节点（换根） 
	u_p(t_r[k].l);//更新新的根的左子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}
void b_r(int &k){//右旋 
	int k_k=t_r[k].l;//存当前节点的左节点 
	t_r[k].l=t_r[k_k].r;//左节点的右子树接到当前节点的左边 
	t_r[k_k].r=k;//当前节点接到做节点的右边 
	k=k_k;//左节点取代当前节点（换根） 
	u_p(t_r[k].r);//更新新的根的右子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}
void n_d(int &k,int v){//加入新节点 
	if(!k){//节点不存在 
		k=n_w(v);//开点 
		return ;
	}
	if(v==t_r[k].v)t_r[k].n++;//权值相同，增加相同节点数 
	else if(v<t_r[k].v){//比当前节点小 
		n_d(t_r[k].l,v);//继续搜 
		if(t_r[k].i_d<t_r[t_r[k].l].i_d)b_r(k);//如果节点优先级更优（旋转） 
	}else {//比当前节点大 
		n_d(t_r[k].r,v);//继续搜 
		if(t_r[k].i_d<t_r[t_r[k].r].i_d)b_l(k);//如果节点优先级更优（旋转）
	}
	u_p(k);//更新节点信息 
}
void c_t(int &k,int v){//删节点 
	if(!k)return ;//节点不存在，跳过 
	if(v==t_r[k].v){//权值相同（找到目标节点） 
		if(t_r[k].n>1){//有多个 
			t_r[k].n--;//直接删 
			u_p(k);//更新节点信息 
			return ;
		}
		if(t_r[k].l||t_r[k].r){//有子树 
			if(!t_r[k].r||t_r[t_r[k].l].i_d>t_r[t_r[k].r].i_d){//右子树不存在，或左子树比右子树优先级高 
				b_r(k);//右旋 
				c_t(t_r[k].r,v);//继续搜 
			}else {//左子树不存在，或者左子树优先级低 
				b_l(k);//左旋 
				c_t(t_r[k].l,v);//继续搜 
			}
			u_p(k);//更新节点信息 
		}else k=0;//没子树直接送走 
		return ;
	}else if(v<t_r[k].v)c_t(t_r[k].l,v);//比当前值小，向左搜 
	else c_t(t_r[k].r,v);//比当前值大，向右搜 
	u_p(k);//更新节点信息 
}
int f_p(int k,int v){//查询 x 的排名 
	if(!k)return 1;//不存在是当前小的数 +1，那么排名就是第一 
	if(v==t_r[k].v)return t_r[t_r[k].l].s_z+1;//找到值，左子树的大小 +1 
	if(v<t_r[k].v)return f_p(t_r[k].l,v);//比当前值小 
	return t_r[t_r[k].l].s_z+t_r[k].n+f_p(t_r[k].r,v);//比当前值大 
}
int f_x(int k,int v){//查询 x 排名的值 
	if(!k)return m_x;//不存在这么多数 
	if(v<=t_r[t_r[k].l].s_z)return f_x(t_r[k].l,v);//排名被左子树大小包含，一定在左子树 
	if(v<=t_r[t_r[k].l].s_z+t_r[k].n)return t_r[k].v;//排名比左子树大，但是不大于左子树大小与当前节点的个数的和，排名包含于当前节点的数量中 
	return f_x(t_r[k].r,v-t_r[t_r[k].l].s_z-t_r[k].n);//排名在右子树中找，先减去一定在排名前的数量 
}
int f_q(int v){//找前驱 
	int k=g_g;//从根节点搜 
	int x_q;//记录前驱（记录答案） 
	while(k){//节点存在 
		if(t_r[k].v<v){//当前节点值比目标值小（可能是结果） 
			x_q=t_r[k].v;//记录 
			k=t_r[k].r;//前往右子树（结果可能更优） 
		}else k=t_r[k].l;//比目标大或等于，前往左子树 
	}
	return x_q;//返回结果 
}
int f_h(int v){//找后继 
	int k=g_g;//从根节点搜 
	int x_h;//记录后继（记录答案） 
	while(k){//当前节点存在 
		if(t_r[k].v>v){//当前节点值比目标值大（可能是结果） 
			x_h=t_r[k].v;//记录 
			k=t_r[k].l;//前往左子树（结果可能更优） 
		}else k=t_r[k].r;//比目标小或等于，前往右子树 
	}
	return x_h;//返回结果 
}
int main(){
	b_t();//初始化平衡树 
	int m=r_r();
	while(m--){
		int op=r_r(),x=r_r();
		if(op==1)n_d(g_g,x);//插入 
		else if(op==2)c_t(g_g,x);//删除 
		else if(op==3)printf("%d\n",f_p(g_g,x)-1);//找排名（初始化时有一个最小值，要减去它的贡献） 
		else if(op==4)printf("%d\n",f_x(g_g,x+1));//找排名为 x 的值（初始化时有一个最小值，要算上它的贡献） 
		else if(op==5)printf("%d\n",f_q(x));//找前驱 
		else printf("%d\n",f_h(x));//找后继 
	}
	return 0;
}

普通平衡树（数据加强）

P6136 【模板】普通平衡树（数据加强版）

大体思路并没有变，注意几个小细节即可。

• 操作4：查询排名为 $x$ 的数（如果不存在，则认为是排名小于 $x$ 的最大数。保证 $x$ 不会超过当前数据结构中数的总数）。

• 本题强制在线，保证所有操作合法（操作 $2$ 保证存在至少一个 $x$，操作 $4,5,6$ 保证存在答案）。

• 我们记 $last$ 表示上一次 $3,4,5,6$ 操作的答案，则每次操作的 $x^, $
  都要异或上 $last$ 才是真实的 $x$。初始 $last$ 为 $0$。

• 本题输入数据较大，请使用较快的读入方式。

操作 $4$ 的处理很容易，如果找的值必当前值大，那么先记下当前值的贡献，取 max，如果最后没找到，那么返回极小值，这样回溯统计答案是不会有贡献，我们也找到额最大值。而如果小于等于，那么久不用取 max，因为答案必然存在。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#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=2e6+10;
const int m_a=2e9+10;
struct po{
	int v;//节点价值 
	int l,r;//左右儿子 
	int s_z;//节点大小 
	int n;//相同节点数量
	int i_d;//随机优先值 
}t_r[o_o];
int x_p;//新节点编号 
int g_g;//根节点 
long long l_t;//存上次操作的答案（解密） 
long long a_s;//统计答案，异或和 
mt19937 m_t(time(0));//随机数种子 
int n_w(int v){//动态开点 
	t_r[++x_p].v=v;//新节点的值 
	t_r[x_p].i_d=m_t()%(o_o<<1);//获取随机优先级 
	t_r[x_p].s_z=1;//初始化大小 
	t_r[x_p].n=1;//初始化相同节点数量 
	return x_p;//返回新节点编号（方便父节点存左右儿子） 
}
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+t_r[k].n;//节点子树大小是左右子树的和加上相同节点个数 
}
void b_t(){
	g_g=n_w(-m_a);//初始化平衡树，放最大最小值 
	t_r[g_g].r=n_w(m_a);
	u_p(g_g);//更新节点子树信息 
}
void b_l(int &k){//左旋 
	int k_k=t_r[k].r;//存当前节点的右节点 
	t_r[k].r=t_r[k_k].l;//右节点的左子树接到当前节点的右边 
	t_r[k_k].l=k;//当前节点接到右节点的左边 
	k=k_k;//右节点取代当前节点（换根） 
	u_p(t_r[k].l);//更新新的根的左子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}
void b_r(int &k){//右旋 
	int k_k=t_r[k].l;//存当前节点的左节点 
	t_r[k].l=t_r[k_k].r;//左节点的右子树接到当前节点的左边 
	t_r[k_k].r=k;//当前节点接到做节点的右边 
	k=k_k;//左节点取代当前节点（换根） 
	u_p(t_r[k].r);//更新新的根的右子树（刚刚进行变动的部分） 
	u_p(k);//更新新根的信息（注意顺序，要先更新它的节点，才能获得最新信息） 
}
void n_d(int &k,int v){//加入新节点 
	if(!k){//节点不存在 
		k=n_w(v);//开点 
		return ;
	}
	if(v==t_r[k].v)t_r[k].n++;//权值相同，增加相同节点数 
	else if(v<t_r[k].v){//比当前节点小 
		n_d(t_r[k].l,v);//继续搜 
		if(t_r[k].i_d<t_r[t_r[k].l].i_d)b_r(k);//如果节点优先级更优（旋转） 
	}else {//比当前节点大 
		n_d(t_r[k].r,v);//继续搜 
		if(t_r[k].i_d<t_r[t_r[k].r].i_d)b_l(k);//如果节点优先级更优（旋转）
	}
	u_p(k);//更新节点信息 
}
void c_t(int &k,int v){//删节点 
	if(!k)return ;//节点不存在，跳过 
	if(v==t_r[k].v){//权值相同（找到目标节点） 
		if(t_r[k].n>1){//有多个 
			t_r[k].n--;//直接删 
			u_p(k);//更新节点信息 
			return ;
		}
		if(t_r[k].l||t_r[k].r){//有子树 
			if(!t_r[k].r||t_r[t_r[k].l].i_d>t_r[t_r[k].r].i_d){//右子树不存在，或左子树比右子树优先级高 
				b_r(k);//右旋 
				c_t(t_r[k].r,v);//继续搜 
			}else {//左子树不存在，或者左子树优先级低 
				b_l(k);//左旋 
				c_t(t_r[k].l,v);//继续搜 
			}
		}else k=0;//没子树直接送走 
	}else if(v<t_r[k].v)c_t(t_r[k].l,v);//比当前值小，向左搜 
	else c_t(t_r[k].r,v);//比当前值大，向右搜 
	u_p(k);//更新节点信息 
}
int f_p(int k,int v){//查询 x 的排名 
	if(!k)return 1;//不存在是当前小的数 +1，那么排名就是第一 
	if(v==t_r[k].v)return t_r[t_r[k].l].s_z+1;//找到值，左子树的大小 +1 
	if(v<t_r[k].v)return f_p(t_r[k].l,v);//比当前值小 
	return t_r[t_r[k].l].s_z+t_r[k].n+f_p(t_r[k].r,v);//比当前值大 
}
int f_x(int k,int v){//查询 x 排名的值
	if(!k)return 0;//找不到，不对答案做贡献 
	if(v<=t_r[t_r[k].l].s_z)return f_x(t_r[k].l,v);//排名被左子树大小包含，一定在左子树 
	if(v<=t_r[t_r[k].l].s_z+t_r[k].n)return t_r[k].v;//排名比左子树大，但是不大于左子树大小与当前节点的个数的和，排名包含于当前节点的数量中 
	return max(t_r[k].v,f_x(t_r[k].r,v-t_r[t_r[k].l].s_z-t_r[k].n));//找最大值，这样可以解决不存在的情况 
}
int f_q(int v){//找前驱 
	int k=g_g;//从根节点搜 
	int x_q;//记录前驱（记录答案） 
	while(k){//节点存在 
		if(t_r[k].v<v){//当前节点值比目标值小（可能是结果） 
			x_q=t_r[k].v;//记录 
			k=t_r[k].r;//前往右子树（结果可能更优） 
		}else k=t_r[k].l;//比目标大或等于，前往左子树 
	}
	return x_q;//返回结果 
}
int f_h(int v){//找后继 
	int k=g_g;//从根节点搜 
	int x_h;//记录后继（记录答案） 
	while(k){//当前节点存在 
		if(t_r[k].v>v){//当前节点值比目标值大（可能是结果） 
			x_h=t_r[k].v;//记录 
			k=t_r[k].l;//前往左子树（结果可能更优） 
		}else k=t_r[k].r;//比目标小或等于，前往右子树 
	}
	return x_h;//返回结果 
}
int main(){
	int n=r_r(),m=r_r();
	b_t();//初始化平衡树 
	for(int i=1;i<=n;i++){//原序列插入树中 
		int v=r_r();
		n_d(g_g,v);//插入 
	}
	while(m--){
		int op=r_r(),v=r_r();
		v^=l_t;
		if(op==1)n_d(g_g,v);//插入 
		else if(op==2)c_t(g_g,v);//删除 
		else if(op==3)l_t=f_p(g_g,v)-1,a_s^=l_t;//找排名（初始化时有一个最小值，要减去它的贡献） 
		else if(op==4)l_t=f_x(g_g,v+1),a_s^=l_t;//找排名为 x 的值（初始化时有一个最小值，要算上它的贡献） 
		else if(op==5)l_t=f_q(v),a_s^=l_t;//找前驱 
		else l_t=f_h(v),a_s^=l_t;//找后继 
	}
	printf("%lld",a_s);
	return 0;
}