当前位置：首页 > news >正文

Splay 平衡树笔记：序列 / 权值两种用法对照

news 2026/3/26 23:21:36

Splay 的核心：用伸展\(splay\)把“最近访问的节点”旋到根，从而实现均摊 \(O(\log n)\) 的动态维护。

1. 共同基础：节点信息与基本旋转 / 伸展

1.1 节点常见字段

ch[2]：左右儿子
fa：父亲
sz：子树大小（用于按排名、区间定位）
cnt：重复计数（权值 splay 常用，序列 splay一般不需要/也可用）
val：值（权值 splay 的键；序列 splay 的 val 可以是字符/数字）
rev：区间翻转 lazy（序列 splay 必备）
sum/min/max：区间信息（按题需要，可加）

1.2 rotate（旋转）

单次旋转把 x 提到父亲位置。Splay 的旋转与 AVL/RB 一样，但要维护 fa、ch、以及更新 pushup()。

1.3 splay（伸展）

把节点 x 旋到目标父亲 goal 的儿子位置（常用：goal=0 表示旋到根）。

Zig：父亲是 goal，旋一次
Zig-Zig：x 与 p 同向，先转 p 再转 x
Zig-Zag：x 与 p 反向，先转 x 再转 x

序列 splay 额外点：必须 pushdown 路径上的 lazy（比如 rev），否则旋转会把未下传的标记打乱。

2. 权值 Splay（按值维护：multiset / order statistics）

2.1 维护目标

像 std::multiset 一样：

插入 / 删除一个值（支持重复）
查询排名（某值是第几小）
查询第 k 小
前驱 / 后继

关键：BST 性质按 val 排序
重复值通常用 cnt 计数，sz = sz(l)+sz(r)+cnt。

2.2 常用操作思路

insert(v)：按 BST 找位置；存在则 cnt++；否则新建节点挂上；最后 splay(x,0)
erase(v)：找到并 splay 到根；若 cnt>1 直接 cnt--；否则合并左右子树
- 合并：若左子树存在，找左子树最大节点 pre，splay(pre,0)，再把右子树接到根的右儿子
kth(k)：根据左子树 sz 和 cnt 走
rank(v)：统计 < v 的数量 + 1（或按你定义）
pre(v)/nxt(v)：先 insert v 或直接在树上走（更推荐直接走），最终 splay 访问节点以优化

2.3 权值 Splay 代码（C++，可直接用）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,cntt,rt;
struct sttt{int ch[2],val,cnt,sz,fa;    
}t[N];
void updt(int x){t[x].sz=t[x].cnt+t[t[x].ch[0]].sz+t[t[x].ch[1]].sz;
}
int is_rt(int x){return t[t[x].fa].ch[1]==x;
}
void rtt(int x){int f=t[x].fa,ff=t[f].fa,wch=is_rt(x);if(ff>0)t[ff].ch[is_rt(f)]=x;int tmp=t[x].ch[wch^1];t[f].ch[wch]=tmp;if(tmp)t[tmp].fa=f;t[x].ch[wch^1]=f;t[f].fa=x;t[x].fa=ff;updt(f);updt(x);
}
void spy(int x){int fa=t[x].fa;while(fa!=0){if(t[fa].fa){if(is_rt(fa)==is_rt(x))rtt(fa);else rtt(x);}rtt(x);fa=t[x].fa;}rt=x;
}
void insert(int x){// cout<<"is "<<x<<'\n';//492737if(rt==0){t[++cntt].cnt=1;t[cntt].val=x;t[cntt].sz=1;rt=cntt;return ;}int u=rt,fa=0;//cout<<t[6].fa<<" "<<t[2].ch[0]<<" "<<t[2].ch[1]<<" "<<'\n';while(1){if(x==t[u].val){t[u].cnt++;updt(u);updt(fa);spy(u);break;}fa=u;u=t[fa].ch[t[fa].val<x];if(!u){cntt++;t[cntt].fa=fa;t[cntt].sz=t[cntt].cnt=1;t[fa].ch[t[fa].val<x]=cntt;t[cntt].val=x;updt(fa);spy(cntt);break;}}
}
int qry_num(int x){int u=rt;while(1){if(t[u].ch[0]&&x<=t[t[u].ch[0]].sz){u=t[u].ch[0];}else{int tmp=t[u].cnt+t[t[u].ch[0]].sz;if(x<=tmp)return t[u].val;x-=tmp;u=t[u].ch[1];}}
}
int qry_rk(int x){int u=rt,ret=0;while(1){if(x<t[u].val){u=t[u].ch[0];}else{ret+=t[t[u].ch[0]].sz;if(x==t[u].val){spy(u);return ret+1;}ret+=t[u].cnt;u=t[u].ch[1];}}
}
void del(int num){//  cout<<"del "<<num<<'\n';//  cout<<num<<"--\n";int x=rt;while(1){if(t[x].val==num)break;else if(t[x].val<num)x=t[x].ch[1];else x=t[x].ch[0];}spy(x);int lp=t[x].ch[0],rp=t[x].ch[1];if(t[x].cnt>1)t[x].cnt--,updt(rt);else if(lp==0&&rp==0){rt=0;}else if(lp==0){rt=rp;t[rp].fa=0;}else if(rp==0){rt=lp;t[lp].fa=0;}else{int maxu=lp;while(t[maxu].ch[1])maxu=t[maxu].ch[1];t[lp].fa=0;t[rp].fa=0;spy(maxu);t[rt].ch[1]=rp;t[rp].fa=rt;updt(rt);}//cout<<x<<"\n";//  cout<<"del "<<num<<'\n';
}
int qry_pre(){int x=t[rt].ch[0];while(t[x].ch[1])x=t[x].ch[1];return t[x].val;
}
int qry_suf(){int x=t[rt].ch[1];while(t[x].ch[0])x=t[x].ch[0];return t[x].val;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;while(n--){int op,x;cin>>op>>x;//     cout<<op<<" "<<x<<'\n';if(op==1)insert(x);else if(op==2)del(x);else if(op==3)insert(x),cout<<qry_rk(x)<<'\n',del(x);else if(op==4)cout<<qry_num(x)<<'\n';else if(op==5){insert(x);cout<<qry_pre()<<'\n';del(x);}else{insert(x);cout<<qry_suf()<<'\n';del(x);}}return 0;
}

3. 序列 Splay（按位置维护：区间翻转/插入/删除/区间查询）

3.1 维护目标

把一个序列（数组/字符串）动态维护：

区间翻转 reverse(l,r)（文艺平衡树经典）
区间赋值 / 区间加（更复杂的 lazy）
区间查询（sum/min/max）
在 pos 插入一段、删除一段、截取一段……

关键：BST 性质按“中序遍历 = 序列顺序”
节点本身不按 val 排序，而是靠 sz 定位第 k 个元素。

3.2 两个哨兵（sentinel）技巧

常用做法：在序列两端加两个“虚拟节点”：

使得任何区间 [l, r] 都能表示为某个节点的子树
具体：令序列下标从 1 开始，构造：[Lsentinel] + 原序列 + [Rsentinel]
区间 [l, r]（原序列）对应：在含哨兵的序列里是 [l+1, r+1]

3.3 区间隔离（核心）

要对 [l, r] 做操作：

x = kth(l)（注意这里的 l 是“含哨兵的排名”）
y = kth(r+2)
splay(x,0) 把 x 旋到根
splay(y,x) 把 y 旋到 x 的右儿子
此时 tr[y].ch[0] 就是区间子树（“被夹在中间的部分”）

3.4 lazy：rev 翻转标记

翻转某个子树：

交换左右儿子
rev ^= 1
并且在访问/旋转之前要 pushdown() 把标记下传。

3.5 序列 Splay 代码（支持区间翻转；可扩展）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,m,cntt,rt;
struct sttt{int ch[2],val,fa,laz,sz;    
}t[N];
int is_rt(int x){return t[t[x].fa].ch[1]==x;
}
void upd(int x){t[x].sz=1+t[t[x].ch[0]].sz+t[t[x].ch[1]].sz;
}
void push_down(int x){if(t[x].laz){t[t[x].ch[0]].laz=t[t[x].ch[0]].laz^1;t[t[x].ch[1]].laz=t[t[x].ch[1]].laz^1;swap(t[x].ch[0],t[x].ch[1]);t[x].laz=0;}
}
void rtt(int x){int f=t[x].fa,g=t[f].fa,xwh=is_rt(x),fwh=is_rt(f);push_down(f),push_down(x);if(g)t[g].ch[fwh]=x;t[x].fa=g;int tmp=t[x].ch[xwh^1];t[f].ch[xwh]=tmp;if(tmp)t[tmp].fa=f;t[x].ch[xwh^1]=f;t[f].fa=x;upd(f),upd(x);
}
void push_all(int x){if(t[x].fa)push_all(t[x].fa);push_down(x);
}
void splay(int x,int up){push_all(x);for(int fa=t[x].fa;fa!=up;fa=t[x].fa){if(t[fa].fa!=up){if(is_rt(fa)==is_rt(x))rtt(fa);else rtt(x);}rtt(x);} if(up==0)rt=x;
}
int kth(int x){int u=rt;while(1){//	cout<<u<<"\n";push_down(u);if(x<=t[t[u].ch[0]].sz){u=t[u].ch[0];}else {int tmp=t[t[u].ch[0]].sz+1;if(x<=tmp){return u;}x-=tmp;u=t[u].ch[1];}}
}
int build(int l,int r,int fa){if(l>r)return 0;int mid=(l+r)/2;int u=++cntt;t[u].fa=fa;if(mid==1||mid==n+2)t[u].val=-1;else t[u].val=mid-1;t[u].ch[0]=build(l,mid-1,u);t[u].ch[1]=build(mid+1,r,u);upd(u);return u;
}
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);cin>>n>>m;rt=build(1,n+2,0);//  cout<<rt<<"\n";while(m--){int l,r;cin>>l>>r;if(l==r)continue;l=kth(l),r=kth(r+2);//cout<<l<<" "<<r<<"\n";splay(l,0);splay(r,l);int pos=t[r].ch[0];t[pos].laz^=1;}for(int i=1;i<=n;i++)cout<<t[kth(i+1)].val<<' ';return 0;
}