学习笔记——平衡树

概述

平衡树是对二叉搜索树的进阶，常规的二叉搜索树在插入一定量的单调性数据后，叶子节点的深度将会不平衡，会出现树退化成链的情况。平衡树通过一系列调整，维持二叉搜索树 \(O(\log n)\) 的复杂度。

\(\text{Splay}\)

介绍

\(\text{Splay}\) 又名伸展树，其操作原理可以感性理解成：对于随机数据，无论怎样的操作都是可以维持平衡的；而对具有单调性的数据，每次操作结束都会将当前操作的点旋转至树根，于是下次查找就会减少冗余的搜索。

模板

首先 \(\text{Splay}\) 的要维护如下几个信息。

rt	tot	fa[x]	ch[x][0/1]	val[x]	cnt[x]	siz[x]
当前根节点编号	新节点编号	父亲节点的编号	两个儿子节点的编号	节点权值	该权值出现的次数	子树大小

常用函数

1. \(\operatorname{maintain}(x)\)

更新节点 \(x\) 的子树大小，不难发现这个值为 \(x\) 左右子树大小和加上 \(x\) 所代表的权值出现次数。

inline void maintain(int x){
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}

2. \(\operatorname{pdson}(x)\)

判断 \(x\) 是其父亲节点的左儿子还是右儿子。

inline bool pdson(int x){
    return x==ch[fa[x]][1];
}

旋转功能函数

1. \(\operatorname{rotate}(x)\)

在此之前，我们先要了解一下旋转的方式。

准确的说，左旋和右旋都是在以旋转的点 \(x\) 的父亲 \(y\) 为根的子树内进行的，显然根据二叉搜索树的性质，子树内无论怎样变化对子树外都没有影响。

我们那左旋来举例，令旋转的节点 \(x\)，父亲节点 \(y\)，两个子节点 \(ch1,ch2\)，对于权值进行排序得到：\(ch1< x< ch2< y\)，我们在左旋之后，\(ch1\) 依旧作为 \(x\) 的左儿子，而 \(y\) 作为 \(x\) 的右儿子，此时的 \(y\) 左儿子已空，而 \(ch2\) 没有父亲，于是连接到 \(y\) 的左儿子，这样的依旧保持 \(ch1 的性质，右旋同理。

接着发现，其实左旋和右旋的难点在于将夹在 \(x\) 与 \(y\) 之间的儿子从 \(x\) 转移至 \(y\)。

我们来考虑如何进行一次旋转，设旋转的点 \(x\)，其父亲 \(y\) 其父亲的父亲 \(z\)，旋转应当分为三步。

将 \(x\) 作为 \(z\) 的子节点（更新 \(x\) 的 \(fa\) 与 \(z\) 的 \(ch\)），此时 \(x\) 更新的身份与 \(y\) 之前的身份相同，于是需要刚刚的 \(\operatorname{pdson}()\) 函数
将 \(y\) 作为 \(x\) 的子节点（更新 \(y\) 的 \(fa\) 与 \(x\) 的 \(ch\)），此时 \(y\) 更新的身份与 \(x\) 之前的身份是相反的（例如 \(x\) 先前为 \(y\) 的左儿子，\(y\) 现在为 \(x\) 的右儿子）
将夹在 \(x\) 与 \(y\) 中间的儿子节点与 \(y\) 相连（此儿子应与 \(x\) 的儿子身份不同，例如 \(x\) 为 \(y\) 的左儿子，现在夹在中间的就是 \(x\) 的右儿子），此时该节点更新的的身份与 \(x\) 之前的身份相同。

inline void rotate(int x){
    int y=fa[x],z=fa[y],chk=pdson(x);
    //x->z
    ch[z][pdson(y)]=x,fa[x]=z;
    //y->x
    ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
    //ch->y
    ch[x][chk^1]=y,fa[y]=x;
    maintain(y),maintain(x);
}

2. \(\operatorname{splay}(x,goal)\)

不断旋转至一点的操作，同样也分 \(3\) 大种情况讨论。

\(x\) 的父亲的父亲 \(z\) 就是旋转的终点，直接左旋或右旋
\(x\) 的父亲 \(y\) 与 \(x\) 的儿子身份相同，即同左或同右，先旋转 \(y\) 再旋转 \(x\)，且旋转方向一致。
\(x\) 的父亲 \(y\) 与 \(x\) 的儿子身份不同，即一左一右或一右一左，两次旋转 \(x\)，且方向不一致。

（细化的话实际分 \(6\) 种小情况，自行画图很好理解）

这样不断旋转直至情况 \(1\)，再旋转一次，就到达目标位置了。

inline void splay(int x,int goal=0){
    while(fa[x]!=goal){
        int y=fa[x],z=fa[y];
        if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
        rotate(x); 
    }
    if(!goal) rt=x;
}

更新和查询函数

1. \(\operatorname{insert}(k)\)

插入一个值为 \(k\) 的数。

既然是二叉搜索树，不断地向下搜索找到最接近的节点，若权值一样，直接将权值出现次数 \(+1\)；反之则新开一个节点（新开时保证是叶子节点）。当然也要判断此时整棵树为空的情况。

inline void insert(int k){
    int x=rt,f=0;
    while(x&&k!=val[x]) f=x,x=ch[x][k>val[x]];
    if(x) cnt[x]++;
    else{
        x=++tot;
        if(f) ch[f][k>val[f]]=x;
        fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
    }
    splay(x);
}

2.\(\operatorname{find}(k)\)

找到权值为 \(k\) 的节点，将其旋转到根。

和查询操作时很相似的，这个功能在后续查前驱后继时也会用到。

inline void find(int k){
      int x=rt;
      if(!x) return;
      while(ch[x][k>val[x]]&&k!=val[x]) x=ch[x][k>val[x]];
      splay(x);
}

3.\(\operatorname{pre_nxt}(k,0/1)\)

查询值 \(k\) 的前驱后继。

操作非常好理解，拿查询前驱举例，将权值为 \(k\) 或接近 \(k\) 的节点旋转至根节点后，在左子树不断向右查询至叶子节点即为前驱，后继同理。注意这里不要把 \(\operatorname{find}(k)\) 与 \(\operatorname{splay}(x)\) 弄混，前者是对权值，后者是对节点编号。

inline int pre_nxt(int k,bool pd){
    find(k);
    int x=rt;
    if(val[x]>k&&pd) return x;
    if(val[x]


4.\(\operatorname{erase}(k)\)
删除一个值为 \(k\) 的数。
操作是将 \(k\) 的前驱后继旋转到相连后，使 \(k\) 的节点没有子树，若有多个直接减少出现次数，反之删点即可。
inline void erase(int k){
    int pre=pre_nxt(k,0),nxt=pre_nxt(k,1);
    splay(pre),splay(nxt,pre);
    int x=ch[nxt][0];
    if(cnt[x]>1){
        cnt[x]--;
        splay(x);
    }
    else ch[nxt][0]=0;
}

5.\(\operatorname{kth}(k)\)
查询排名为 \(k\) 的数。
无脑向下找，思路同权值线段树。
inline int kth(int k){
    int x=rt;
    if(siz[x]siz[ch[x][0]]+cnt[x]){
            k-=siz[ch[x][0]]+cnt[x];
            x=ch[x][1];
        }
        else if(k<=siz[ch[x][0]]) x=ch[x][0];
        else return val[x];
    }
}

例题
1.P3369 【模板】普通平衡树
操作与上述相同，要先插入一个极大值、极小值作为边界。

点击查看代码
int rt,tot;
struct Splay{
	int fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],siz[maxn];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x); 
		}
		if(!goal) rt=x;
	}
	inline void insert(int k){
		int x=rt,f=0;
		while(x&&k!=val[x]) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(f) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		splay(x);
	}
	inline void find(int k){
		int x=rt;
		if(!x) return;
		while(ch[x][k>val[x]]&&k!=val[x]) x=ch[x][k>val[x]];
		splay(x);
	}
	inline int pre_nxt(int k,bool pd){
		find(k);
		int x=rt;
		if(val[x]>k&&pd) return x;
		if(val[x]1){
			cnt[x]--;
			splay(x);
		}
		else ch[nxt][0]=0;
	}
	inline int kth(int k){
		int x=rt;
		if(siz[x]siz[ch[x][0]]+cnt[x]){
				k-=siz[ch[x][0]]+cnt[x];
				x=ch[x][1];
			}
			else if(k<=siz[ch[x][0]]) x=ch[x][0];
			else return val[x];
		}
	}
}tree;
int n;
int main(){
	n=read();
	tree.insert(maxxn),tree.insert(minxn);
	for(int i=1;i<=n;i++){
		int opt=read(),x=read();
		if(opt==1) tree.insert(x);
		if(opt==2) tree.erase(x);
		if(opt==3){
			tree.find(x);
			printf("%d\n",tree.siz[tree.ch[rt][0]]);
		}
		if(opt==4) printf("%d\n",tree.kth(x+1));
		if(opt==5) printf("%d\n",tree.val[tree.pre_nxt(x,0)]);
		if(opt==6) printf("%d\n",tree.val[tree.pre_nxt(x,1)]);
	}
	return 0;
}


2.P6136 【模板】普通平衡树（数据加强版）
稍微有修改，除了强制在线，不保证查询数据一定存在，所有查排名时要先插入再删除。

点击查看代码
int rt,tot;
struct Splay{
	int fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],siz[maxn];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x); 
		}
		if(!goal) rt=x;
	}
	inline void insert(int k){
		int x=rt,f=0;
		while(x&&k!=val[x]) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(f) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		splay(x);
	}
	inline void find(int k){
		int x=rt;
		if(!x) return;
		while(ch[x][k>val[x]]&&k!=val[x]) x=ch[x][k>val[x]];
		splay(x);
	}
	inline int pre_nxt(int k,bool tp){
		find(k);
		int x=rt;
		if(val[x]>k&&tp) return x;
		if(val[x]1){
			cnt[x]--;
			splay(x);
		}
		else ch[nxt][0]=0;
	}
	inline int kth(int k){
		int x=rt;
		if(siz[x]siz[ch[x][0]]+cnt[x]){
				k-=siz[ch[x][0]]+cnt[x];
				x=ch[x][1];
			}
			else if(k<=siz[ch[x][0]]) x=ch[x][0];
			else return val[x];
		}
	}
}tree;
int n,m;
int a[maxn],ans;
int main(){
	n=read(),m=read();
	tree.insert(maxxn),tree.insert(minxn);
	for(int i=1;i<=n;i++){
		a[i]=read();
		tree.insert(a[i]);
	}
	int last=0;
	for(int i=1;i<=m;i++){
		int opt=read(),x=read()^last;
		if(opt==1) tree.insert(x);
		if(opt==2) tree.erase(x);
		if(opt==3){
			tree.insert(x);
			tree.find(x);
			last=tree.siz[tree.ch[rt][0]];
			tree.erase(x);
			ans^=last;
		}
		if(opt==4){
			last=tree.kth(x+1);
			ans^=last;
		}
		if(opt==5){
			last=tree.val[tree.pre_nxt(x,0)];
			ans^=last;
		}
		if(opt==6){
			last=tree.val[tree.pre_nxt(x,1)];
			ans^=last;
		}
	}
	printf("%d\n",ans);
	return 0;
}


3、P2234 HNOI2002 营业额统计
简单的查询一下前驱后继，注意这里可以是与其权值相同的，然后再插入新的权值。

点击查看代码
int rt,tot;
struct Splay{
	int fa[40005],ch[40005][2],val[40005],cnt[40005],siz[40005];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x);
		}
		if(!goal) rt=x;
	}
	inline void insert(int k){
		int x=rt,f=0;
		while(x&&val[x]!=k) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(f) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		splay(x);
	}
	inline void find(int k){
		int x=rt;
		if(!rt) return;
		while(ch[x][k>val[x]]&&val[x]!=k) x=ch[x][k>val[x]];
		splay(x);
	}
	inline int pre_nxt(int k,bool pd){
		find(k);
		int x=rt;
		if(val[x]==k) return x;
		if(val[x]>k&&pd) return x;
		if(val[x]


4、P2286 HNOI2004 宠物收养场
看样子要维护两棵平衡树——关于宠物和关于主人的，然而考虑到待领养的只有主人或宠物一种，给当前的平衡树一个状态，判断平衡树是否为空并修改状态即可。
注意这里有删除操作，于是查询前驱后继时，要考虑是否计算与查询权值相等的。

点击查看代码
int rt,tot;
struct Splay{
	ll fa[80005],ch[80005][2],val[80005],cnt[80005],siz[80005];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x); 
		}
		if(!goal) rt=x;
	}
	inline void insert(ll k){
		int x=rt,f=0;
		while(x&&k!=val[x]) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(f) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		splay(x);
	}
	inline void find(ll k){
		int x=rt;
		if(!x) return;
		while(ch[x][k>val[x]]&&k!=val[x]) x=ch[x][k>val[x]];
		splay(x);
	}
	inline int pre_nxt(int k,bool pd,bool pd2=0){
		find(k);
		int x=rt;
		if(val[x]==k&&pd2) return x;
		if(val[x]>k&&pd) return x;
		if(val[x]1){
			cnt[x]--;
			splay(x);
		}
		else ch[nxt][0]=0;
	}
}tree;
int n;
ll ans;
int tp,cnt;
int main(){
	n=read();
	tree.insert(maxxn),tree.insert(minxn);
	for(int i=1;i<=n;i++){
		int opt=read();
		ll x=read();
		if(cnt==0){
			tree.insert(x);
			tp=opt;
			cnt++;
		}
		else if(tp==opt){
			tree.insert(x);
			cnt++;
		}
		else{
			int pos1=tree.pre_nxt(x,0,1),pos2=tree.pre_nxt(x,1,1);
			ll num1=tree.val[pos1],num2=tree.val[pos2];
			if(llabs(num1-x)<=llabs(num2-x)){
				ans=(ans+llabs(num1-x))%mod;
				tree.erase(num1);	
			}
			else{
				ans=(ans+llabs(num2-x))%mod;
				tree.erase(num2);
			}
			cnt--;
		}	
	}
	printf("%lld\n",ans);
	return 0;
}


5.P1486 NOI2004 郁闷的出纳员
与板子不同的地方：查询第 \(k\) 大，删除操作是小于 \(\min\) 的全部数据。
第一个不同直接简单修改一下向下搜索的判断即可，第二个操作考虑找到边界的后继，把剩余部分直接断边即可。
注意：插入时不能插入小于 \(\min\) 的数据。

点击查看代码
int rt,tot;
int n,lim,ans;
struct Splay{
	int fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],siz[maxn];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x);
		}
		if(!goal) rt=x; 
	}
	inline void insert(int k){
		int x=rt,f=0;
		while(x&&val[x]!=k) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(fa) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		splay(x);
	}
	inline void find(int k){
		int x=rt;
		if(!rt) return;
		while(ch[x][k>val[x]]&&val[x]!=k) x=ch[x][k>val[x]];
		splay(x);
	}
	inline int pre_nxt(int k,bool pd,bool pd2=0){
		find(k);
		int x=rt;
		if(val[x]==k&&pd2) return x;
		if(val[x]>k&&pd) return x;
		if(val[x]siz[ch[x][1]]+cnt[x]){
				k-=siz[ch[x][1]]+cnt[x];
				x=ch[x][0];
			}
			else if(k<=siz[ch[x][1]]) x=ch[x][1];
			else return val[x];
		}
	}
	inline void add(int k){
		for(int i=1;i<=tot;i++) val[i]+=k;
	}
	inline void erase(int k){
		int x=pre_nxt(k+lim,1,1);
		splay(x);
		ans+=siz[ch[x][0]];
		ch[x][0]=0;
		maintain(x);
		add(-k);
	}
}tree;
int main(){
	n=read(),lim=read();
	tree.insert(maxxn);
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		int x=read();
		if(ch=='I'&&x>=lim) tree.insert(x);
		if(ch=='A') tree.add(x);
		if(ch=='S') tree.erase(x);
		if(ch=='F') printf("%d\n",tree.kth(x+1));
	}
	printf("%d\n",ans);
	return 0;
}


6.P3391 【模板】文艺平衡树
区间翻转操作。
首先很明显的是，把区间作为子树的话，将每个节点的左右子树都交换，就能实现这个操作。于是可以打上翻转的懒标记，接着近似于删除一个点的操作一样，我们把区间 \([L,R]\) 独立出来的操作是：将区间前驱旋转至根，再将区间后继旋转至当前根（也就是区间前驱），按中序遍历输出即可。

点击查看代码
int n,m;
int rt,tot;
struct Splay{
	int fa[maxn],ch[maxn][2],val[maxn],siz[maxn],mark[maxn];
	inline void maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void push_down(int x){
		if(mark[x]){
			mark[x]=0;
			mark[ch[x][0]]^=1,mark[ch[x][1]]^=1;
			swap(ch[x][0],ch[x][1]);
		}
	}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x);
		}
		if(!goal) rt=x;
	}
	inline void insert(int k){
		int x=rt,f=0;
		while(x) f=x,x=ch[x][k>val[x]];
		x=++tot;
		if(f) ch[f][k>val[f]]=x;
		fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,siz[x]=1,mark[x]=0;
		splay(x);
	}
	inline int kth(int k){
		int x=rt;
		while(1){
			push_down(x);
			if(k>siz[ch[x][0]]+1){
				k-=siz[ch[x][0]]+1;
				x=ch[x][1];
			}
			else if(k<=siz[ch[x][0]]) x=ch[x][0];
			else return x;
		}
	}
	inline void print(int x){
		push_down(x);
		if(ch[x][0]) print(ch[x][0]);
		if(val[x]>1&&val[x]


7.P3380 【模板】二逼平衡树（树套树）
需要支持区间 \([L,R]\) 中数据的排名、排名对应的数据、前驱后继以及单点修改。
需要线段树套平衡树，即在线段树的每个区间中，选择用平衡树来维护。
（1） 查询数据 \(k\) 在区间 \([L,R]\) 的排名
首先 \(k\) 的排名等价于，小于 \(k\) 的数据的个数 \(+1\)，于是我们这个可以拆成若干个区间（线段树所维护的），求和即可。
inline int Seg_rank(int id,int l,int r,int pl,int pr,int k){
    if(pl<=l&&r<=pr){
        Splay_find(id,k);
        int x=rt[id];
        if(k<=val[x]) return siz[ch[x][0]]-1;
        else return siz[ch[x][0]]+cnt[x]-1;
    }
    int res=0;
    if(pl<=mid) res+=Seg_rank(lson,pl,pr,k);
    if(pr>mid) res+=Seg_rank(rson,pl,pr,k); 
    return res;
}

（2）查询区间 \([L,R]\) 中排名为 \(k\) 的数
这样的查询在跨区间的线段树中是不可行的，我们二分这个排名，然后进行查询排名操作直到找到答案。
inline int Seg_kth(int pl,int pr,int k){
    int l=0,r=1e8,res;
    while(l<=r){
        if(Seg_rank(1,1,n,pl,pr,mid)+1>k) r=mid-1;
        else res=mid,l=mid+1;
    }
    return res;
}

（3）修改位置 \(p\) 上的值为 \(k\)
非常简单，每个包含的区间都去修改即可。
inline void Seg_update(int id,int l,int r,int p,int k){
		Splay_erase(id,a[p]),Splay_insert(id,k);
		if(l==r){
			a[l]=k;
			return;
		}
		if(p<=mid) Seg_update(lson,p,k);
		else Seg_update(rson,p,k);
	}

（4）查询 \(k\) 在区间 \([L,R]\) 的前驱后继
前驱后继实质是一个数值，于是找每个区间的前驱最大值和后继最小值即可。
inline int Seg_pre(int id,int l,int r,int pl,int pr,int k){
    if(pl<=l&&r<=pr) return val[Splay_pre_nxt(id,k,0)];
    int res=minxn;
    if(pl<=mid) res=max(res,Seg_pre(lson,pl,pr,k));
    if(pr>mid) res=max(res,Seg_pre(rson,pl,pr,k));
    return res;
}
inline int Seg_nxt(int id,int l,int r,int pl,int pr,int k){
    if(pl<=l&&r<=pr) return val[Splay_pre_nxt(id,k,1)];
    int res=maxxn;
    if(pl<=mid) res=min(res,Seg_nxt(lson,pl,pr,k));
    if(pr>mid) res=min(res,Seg_nxt(rson,pl,pr,k));
    return res;
}


点击查看代码
int n,q;
int a[maxn];
int tot;
struct SegmentTree_Splay{
	int fa[maxm],ch[maxm][2],val[maxm],cnt[maxm],siz[maxm],rt[maxn];
	inline void Splay_maintain(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline bool Splay_pdson(int x){return x==ch[fa[x]][1];}
	inline void Splay_rotate(int x){
		int y=fa[x],z=fa[y],chk=Splay_pdson(x);
		ch[z][Splay_pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		Splay_maintain(y),Splay_maintain(x);
	}
	inline void Splay_splay(int id,int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) Splay_rotate(Splay_pdson(x)==Splay_pdson(y)?y:x);
			Splay_rotate(x); 
		}
		if(!goal) rt[id]=x;
	}
	inline void Splay_insert(int id,int k){
		int x=rt[id],f=0;
		if(!x){
			x=++tot;
			fa[x]=0,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
			rt[id]=x;
			return;
		}
		while(x&&val[x]!=k) f=x,x=ch[x][k>val[x]];
		if(x) cnt[x]++;
		else{
			x=++tot;
			if(f) ch[f][k>val[f]]=x;
			fa[x]=f,ch[x][0]=ch[x][1]=0,val[x]=k,cnt[x]=siz[x]=1;
		}
		Splay_splay(id,x);
	}
	inline void Splay_find(int id,int k){
		int x=rt[id];
		if(!x) return;
		while(ch[x][k>val[x]]&&k!=val[x]) x=ch[x][k>val[x]];
		Splay_splay(id,x);
	}
	inline int Splay_pre_nxt(int id,int k,bool pd){
		Splay_find(id,k);
		int x=rt[id];
		if(val[x]>k&&pd) return x;
		if(val[x]1){
			cnt[x]--;
			Splay_splay(id,x);
		} 
		else ch[nxt][0]=0;
	}
	#define mid ((l+r)>>1)
	#define lson id<<1,l,mid
	#define rson id<<1|1,mid+1,r
	inline void Seg_build(int id,int l,int r){
		Splay_insert(id,maxxn),Splay_insert(id,minxn);
		if(l==r) return;
		Seg_build(lson),Seg_build(rson);
	}
	inline void Seg_insert(int id,int l,int r,int p,int k){
		Splay_insert(id,k);
		if(l==r) return;
		if(p<=mid) Seg_insert(lson,p,k);
		else Seg_insert(rson,p,k);
	}
	inline int Seg_rank(int id,int l,int r,int pl,int pr,int k){
		if(pl<=l&&r<=pr){
			Splay_find(id,k);
			int x=rt[id];
			if(k<=val[x]) return siz[ch[x][0]]-1;
			else return siz[ch[x][0]]+cnt[x]-1;
		}
		int res=0;
		if(pl<=mid) res+=Seg_rank(lson,pl,pr,k);
		if(pr>mid) res+=Seg_rank(rson,pl,pr,k); 
		return res;
	}
	inline void Seg_update(int id,int l,int r,int p,int k){
		Splay_erase(id,a[p]),Splay_insert(id,k);
		if(l==r){
			a[l]=k;
			return;
		}
		if(p<=mid) Seg_update(lson,p,k);
		else Seg_update(rson,p,k);
	}
	inline int Seg_pre(int id,int l,int r,int pl,int pr,int k){
		if(pl<=l&&r<=pr) return val[Splay_pre_nxt(id,k,0)];
		int res=minxn;
		if(pl<=mid) res=max(res,Seg_pre(lson,pl,pr,k));
		if(pr>mid) res=max(res,Seg_pre(rson,pl,pr,k));
		return res;
	}
	inline int Seg_nxt(int id,int l,int r,int pl,int pr,int k){
		if(pl<=l&&r<=pr) return val[Splay_pre_nxt(id,k,1)];
		int res=maxxn;
		if(pl<=mid) res=min(res,Seg_nxt(lson,pl,pr,k));
		if(pr>mid) res=min(res,Seg_nxt(rson,pl,pr,k));
		return res;
	}
	inline int Seg_kth(int pl,int pr,int k){
		int l=0,r=1e8,res;
		while(l<=r){
			if(Seg_rank(1,1,n,pl,pr,mid)+1>k) r=mid-1;
			else res=mid,l=mid+1;
		}
		return res;
	}
}tree;
int main(){
	n=read(),q=read();
	tree.Seg_build(1,1,n);
	for(int i=1;i<=n;i++){
		a[i]=read();
		tree.Seg_insert(1,1,n,i,a[i]);
	}
	while(q--){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),k=read();
			printf("%d\n",tree.Seg_rank(1,1,n,l,r,k)+1);
		}
		if(opt==2){
			int l=read(),r=read(),k=read();
			printf("%d\n",tree.Seg_kth(l,r,k));
		}
		if(opt==3){
			int p=read(),k=read();
			tree.Seg_update(1,1,n,p,k);
		}
		if(opt==4){
			int l=read(),r=read(),k=read();
			printf("%d\n",tree.Seg_pre(1,1,n,l,r,k));
		}
		if(opt==5){
			int l=read(),r=read(),k=read();
			printf("%d\n",tree.Seg_nxt(1,1,n,l,r,k));
		}
	}
	return 0;
}


8.P4036 JSOI2008 火星人
首先这个求 \(\operatorname{LCQ(x,y)}\) 显然可以二分求哈希，发现排序关键字直接瞎搞，强行维护一下序列即可。
最主要的是掌握对于单点和子树修改时，空出修改的部分使其独立，方式是查找前驱后继（本题是第 \(k\) 大）并旋转到梗，其他看代码吧。

点击查看代码
ull p[maxn];
int q;
int rt,tot;
struct Splay{
	int fa[maxn],ch[maxn][2],len[maxn],siz[maxn];
	ull val[maxn],h[maxn];
	inline void init(){
		ch[1][1]=2,fa[2]=1;
		rt=1,tot=2;
		maintain(2),maintain(1);
	}
	inline void maintain(int x){
		siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
		len[x]=len[ch[x][0]]+len[ch[x][1]]+((x>2)?1:0);
		h[x]=(h[ch[x][0]]*base1+val[x])*p[len[ch[x][1]]]+h[ch[x][1]]; 
	}
	inline bool pdson(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],chk=pdson(x);
		ch[z][pdson(y)]=x,fa[x]=z;
		ch[y][chk]=ch[x][chk^1],fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y,fa[y]=x;
		maintain(y),maintain(x);
	}
	inline void splay(int x,int goal=0){
		while(fa[x]!=goal){
			int y=fa[x],z=fa[y];
			if(z!=goal) rotate(pdson(x)==pdson(y)?y:x);
			rotate(x);
		}
		if(!goal) rt=x;
		maintain(x);
	}
	inline int kth(int k){
		int x=rt;
		while(1){
			if(k>siz[ch[x][0]]+1){
				k-=siz[ch[x][0]]+1;
				x=ch[x][1]; 
			}
			else if(k<=siz[ch[x][0]]) x=ch[x][0];
			else return x;
		}
	}
	inline void insert(int x,int k){
		int pre=kth(x+1),nxt=kth(x+2);//插入位置的前一个字符为x，实质的位置为x+1，后面一个字符位置是x+2，旋转之后空出了x+1与x+2的空间
		splay(pre),splay(nxt,pre);
		fa[++tot]=nxt,ch[nxt][0]=tot,val[tot]=k;
		splay(tot);
	}
	inline ull get_h(int x,int len){
		int pre=kth(x),nxt=kth(x+len+1);//查询区间[x+1,x+len]，前驱后继分别为x和x+len+1，空出检索的子树
		splay(pre),splay(nxt,pre);
		return h[ch[nxt][0]];
	}
	inline void update(int x,int k){
		int pre=kth(x),nxt=kth(x+2);//更新字符x，实际位置x+1，前驱后继分别为x和x+2，空出更新的字符位置
		splay(pre),splay(nxt,pre);
		val[ch[nxt][0]]=k;
		maintain(ch[nxt][0]);
		maintain(nxt),maintain(pre);
	}
	inline int query(int x,int y){
		int l=0,r=tot-max(x,y)-1,res;
		while(l<=r){
			int mid=(l+r)>>1;
			if(get_h(x,mid)==get_h(y,mid)){
				l=mid+1;
				res=mid;
			}
			else r=mid-1;
		}
		return res;
	}
}tree;
char s[maxn];
int main(){
	p[0]=1;
	for(int i=1;i<=maxn;i++){
		p[i]=p[i-1]*base1;
	}
	tree.init();//先插入两个边界值
	scanf("%s",s+1);
	for(int i=1;i<=strlen(s+1);i++){
		tree.insert(i-1,s[i]);
	}
	q=read();
	while(q--){
		char ch[2];
		scanf("%s",ch);
		if(ch[0]=='Q'){
			int x=read(),y=read();
			printf("%d\n",tree.query(x,y));
		}
		else if(ch[0]=='R'){
			int x=read(),c;
			scanf("%s",ch);
			c=ch[0];
			tree.update(x,c);
		}
		else{
			int x=read(),c;
			scanf("%s",ch);
			c=ch[0];
			tree.insert(x,c);
		}
	}
	return 0;
}


					
					
					
						相关
						
				
						
			
																
								
										Git--学习笔记（三）远程仓库克隆到本地
									
									
								 

        
								
							
							

																
								
										数据结构--栈（C语言实现）
									
									
								 

        
								
							
							

																
								
										[学习笔记] 整数规划之割平面法 How and why?
									
									
								 

        
								
							
							

																
								
										计网学习笔记(5) - 物理层与媒介
									
									
								 

        
								
							
							

																
								
										selenium python学习笔记之八 窗口截图、验证码处理
									
									
								 

        
								
							
							

																
								
										AntDesign vue学习笔记（三）嵌套路由使用
									
									
								 

        
								
							
							

																
								
										vue学习笔记（一）--来源尚硅谷
									
									
								 

        
								
							
							

																
								
										【学习笔记】TSlib校准原理
									
									
								 

        
								
							
							

																
								
										Go语言核心36讲（Go语言实战与应用六）--学习笔记
									
									
								 

        
								
							
							

																
								
										docker 学习笔记-7
									
									
								 

        
								
							
							

																
								
										数据结构----单链表升级版
									
									
								 

        
								
							
							

																
								
										数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

学习笔记——平衡树

概述

\(\text{Splay}\)

介绍

模板

常用函数

1. \(\operatorname{maintain}(x)\)

2. \(\operatorname{pdson}(x)\)

旋转功能函数

1. \(\operatorname{rotate}(x)\)

2. \(\operatorname{splay}(x,goal)\)

更新和查询函数

1. \(\operatorname{insert}(k)\)

2.\(\operatorname{find}(k)\)

3.\(\operatorname{pre_nxt}(k,0/1)\)

4.\(\operatorname{erase}(k)\)

5.\(\operatorname{kth}(k)\)

例题

1.P3369 【模板】普通平衡树

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

3、P2234 HNOI2002 营业额统计

4、P2286 HNOI2004 宠物收养场

5.P1486 NOI2004 郁闷的出纳员

6.P3391 【模板】文艺平衡树

7.P3380 【模板】二逼平衡树（树套树）

（1） 查询数据 \(k\) 在区间 \([L,R]\) 的排名

（2）查询区间 \([L,R]\) 中排名为 \(k\) 的数

（3）修改位置 \(p\) 上的值为 \(k\)

（4）查询 \(k\) 在区间 \([L,R]\) 的前驱后继

8.P4036 JSOI2008 火星人

相关

（1）查询数据 \(k\) 在区间 \([L,R]\) 的排名