前言
噫，好！我又来了
这几天闲着没事翻桃片，发现好多人卡评测被封了，就看了看紫荆花，发现 splay 会被卡，就去学了替罪羊树（\(\text{Scapegoat Tree}\)）。
正文
写在前面
大家都知道，splay 是通过旋转维护整棵树的平衡，但也会出现深度过大而导致复杂度爆炸的情况。
而替罪羊树则是通过重构来维护平衡，他会初始一个失衡系数 \(\alpha\)，一般取 \([0.7,0.8]\)，然后通过比较左右子树大小和自身大小来判断是否失衡，若失衡，就拍扁重构
然后是关于删除的一个问题，替罪羊树用的是惰性删除（把当前节点个数清零，但不从树中删去），记住这个东西，对之后的很多东西是都有影响的。
关于结构体
struct Node {
int val,num,ch[2],sizt,sizv,siznd;
}t[2000001];
可以发现，基本上与 splay 没有什么太大区别，但多了，三个 siz 并且没有 fa（因为他不需要遍历父亲）。
解读一下这三个 siz。
-
sizt：子树中有多少个不同的权值（包括空节点） -
sizv：子树中有多少个节点（不包括空节点） -
siznd：子树中有多少个不同的权值（不包括空节点）
对应的 upd 应该这么写
void upd(int x) {
t[x].sizt=t[t[x].ch[0]].sizt+t[t[x].ch[1]].sizt+1;
t[x].sizv=t[t[x].ch[0]].sizv+t[t[x].ch[1]].sizv+t[x].num;
t[x].siznd=t[t[x].ch[0]].siznd+t[t[x].ch[1]].siznd+(t[x].num>=1);
}
关于重构
就是把一棵树展开进一个线性表中，再二分建树（空节点不建树），比较简单，直接上代码了。
void rbuflatten(int x) {
if (!x) return;
rbuflatten(t[x].ch[0]);
if (t[x].num) lur[++luc]=x;
rbuflatten(t[x].ch[1]);
}
int rbubuild(int l,int r) {
if (l==r) return 0;
int mid=(l+r>>1);
t[lur[mid]].ch[0]=rbubuild(l,mid);
t[lur[mid]].ch[1]=rbubuild(mid+1,r);
upd(lur[mid]);
return lur[mid];
}
void rbu(int &x) { luc=0,rbuflatten(x),x=rbubuild(1,luc+1); }
判断是否重构有三个条件
-
本节点是否为空
-
自己的
sizt乘上 \(\alpha\) 是否小于左右子树中最大的子树的sizt -
自己的
sizt乘上 \(\alpha\) 是否大于自己的siznd
关于第三条，因为惰性删除，删除操作一旦过多，会导致树中的空节点过多，显而易见，空节点多没有用，所以，可通过重构操作删去。
bool ifrbu(int x) { return (t[x].num and ((t[x].sizt*A<=(double)std::max(t[t[x].ch[0]].sizt,t[t[x].ch[1]].sizt)) or (t[x].sizt*A>=(double)t[x].siznd))); }
查询排名
替罪羊树有两个函数，一个为 rkf，是查询比 \(k\) 小的数中最大数的排名，一个是 rkl，是查询比 \(k\) 大的数中最小数的排名。
两个函数写法基本相同，\(k\) 比本节点大往右子树搜，比本节点小往左子树搜。
但是！替罪羊树采用惰性删除，所以显而易见的，当 \(k\) 等于本节点时如果 num 不等于 \(0\) 是可以返回的，但如果等于 \(0\) 呢？
两个函数有两个不同的写法。
对于 rkf 因为他是要找比 \(k\) 小的数中的最大数的排名，所以他的返回值为本节点的左子树的 sizv，那如果 \(k\) 所代表的节点的 num 为 \(0\)，那么他的左子树的 sizv，就等于比 \(k\) 大的数中的最小数所代表节点的左子树的 sizv，所以应该往右子树搜。
对于 rkl 因为他是要找比 \(k\) 大的数中的最小数的排名，所以他的返回值应为本节点的左子树的 sizv 加上自己的 num 再加 \(1\)，那如果 \(k\) 所代表的节点的 num 为 \(0\)，那么他的左子树大小，就等于比他小的数中最大数所代表节点的左子树的 sizv 加上自己的 num，所以要往左子树搜。
代码如下：
int rkf(int x,int k) {
if (!x) return 0;
else {
if (t[x].val==k and t[x].num) return t[t[x].ch[0]].sizv;
else if (k<t[x].val) return rkf(t[x].ch[0],k);
else return rkf(t[x].ch[1],k)+t[t[x].ch[0]].sizv+t[x].num;
}
}
int rkl(int x,int k) {
if (!x) return 1;
else {
if (t[x].val==k and t[x].num) return t[t[x].ch[0]].sizv+t[x].num+1;
else if (k>t[x].val) return rkl(t[x].ch[1],k)+t[t[x].ch[0]].sizv+t[x].num;
else return rkl(t[x].ch[0],k);
}
}
查询排名为 \(k\) 的权值
没什么好说的，查看 \(k\) 是否在 \((sizv_{\text{左子树}},sizv_{\text{左子树}}+num_{\text{本节点}}]\) 即可，如果小往左子树搜，大则往右子树搜。
int kth(int x,int k) {
if (!x) return 0;
else {
if (t[t[x].ch[0]].sizv<k and k<=t[t[x].ch[0]].sizv+t[x].num) return t[x].val;
else if (t[t[x].ch[0]].sizv>=k) return kth(t[x].ch[0],k);
else return kth(t[x].ch[1],k-t[t[x].ch[0]].sizv-t[x].num);
}
}
前驱以及后继
结合一下上面的三个函数即可。
int pre(int x) { return kth(rt,rkf(rt,x)); }
int nxt(int x) { return kth(rt,rkl(rt,x)); }
插入
比较简单，递归插入即可，不多说了。
回溯时记得重构。
void ins(int &x,int k) {
if (!x) {
t[x=++cnt].val=k,t[x].num++;
upd(x);
return;
} else {
if (k==t[x].val) t[x].num++;
else if (k>t[x].val) ins(t[x].ch[1],k);
else ins(t[x].ch[0],k);
upd(x);
if (ifrbu(x)) rbu(x);
}
}
删除
同上
void del(int &x,int k) {
if (!x) return;
if (k==t[x].val) t[x].num--;
else if (k>t[x].val) del(t[x].ch[1],k);
else del(t[x].ch[0],k);
upd(x);
if (ifrbu(x)) rbu(x);
}
例题
以后没准会更新，但 \(99.9\%\) 会咕。
板子。
#include <iostream>
#include <cstdio>
namespace Scapegoat_tree {
const double A=0.75;
struct Node {
int val,ch[2],num,sizt,sizv,siznd;
}t[100001];
int cnt,rt,ldc,ldr[100001];
void upd(int x) {
t[x].sizt=t[t[x].ch[0]].sizt+t[t[x].ch[1]].sizt+1;
t[x].sizv=t[t[x].ch[0]].sizv+t[t[x].ch[1]].sizv+t[x].num;
t[x].siznd=t[t[x].ch[0]].siznd+t[t[x].ch[1]].siznd+(t[x].num>=1);
}
bool ifrbu(int x) { return (t[x].num and ((t[x].sizt*A<=(double)std::max(t[t[x].ch[0]].sizt,t[t[x].ch[1]].sizt)) or (t[x].sizt*A>=(double)t[x].siznd))); }
void rbuflatten(int x) {
if (!x) return;
rbuflatten(t[x].ch[0]);
if (t[x].num) ldr[++ldc]=x;
rbuflatten(t[x].ch[1]);
}
int rbubuild(int l,int r) {
if (l>=r) return 0;
int mid=(l+r>>1);
t[ldr[mid]].ch[0]=rbubuild(l,mid);
t[ldr[mid]].ch[1]=rbubuild(mid+1,r);
upd(ldr[mid]);
return ldr[mid];
}
void rbu(int &x) {
ldc=0;
rbuflatten(x);
x=rbubuild(1,ldc+1);
}
void ins(int &x,int k) {
if (!x) {
t[x=++cnt].val=k,t[x].num++;
upd(x);
} else {
if (k==t[x].val) t[x].num++;
else if (k>t[x].val) ins(t[x].ch[1],k);
else ins(t[x].ch[0],k);
upd(x);
if (ifrbu(x)) rbu(x);
}
}
void del(int &x,int k) {
if (!x) return;
if (t[x].val==k) t[x].num--;
else if (k>t[x].val) del(t[x].ch[1],k);
else del(t[x].ch[0],k);
upd(x);
if (ifrbu(x)) rbu(x);
}
int rkf(int x,int k) {
if (!x) return 0;
else {
if (t[x].num and t[x].val==k) return t[t[x].ch[0]].sizv;
else if (t[x].val>k) return rkf(t[x].ch[0],k);
else if (t[x].val<=k) return t[t[x].ch[0]].sizv+t[x].num+rkf(t[x].ch[1],k);
}
}
int rkl(int x,int k) {
if (!x) return 1;
else {
if (t[x].num and t[x].val==k) return t[t[x].ch[0]].sizv+t[x].num+1;else if (t[x].val<k) return t[t[x].ch[0]].sizv+t[x].num+rkl(t[x].ch[1],k);
else/* if (t[x].val>k) */return rkl(t[x].ch[0],k);
}
return 1;
}
int kth(int x,int k) {
if (!x) return 0;
else {
if (/*t[x].num and */t[t[x].ch[0]].sizv<k and k<=t[t[x].ch[0]].sizv+t[x].num) return t[x].val;
else if (t[t[x].ch[0]].sizv>=k) return kth(t[x].ch[0],k);
else return kth(t[x].ch[1],k-t[t[x].ch[0]].sizv-t[x].num);
}
}
int pre(int x) {
int ra=rkf(rt,x);
return kth(rt,ra);
}
int nxt(int x) {
int ra=rkl(rt,x);
return kth(rt,ra);
}
}
using namespace Scapegoat_tree;
using namespace std;
int n;
void work(int x) {
if (!x) return;
work(t[x].ch[0]);
if (t[x].num) printf("%d ",t[x].val);
work(t[x].ch[1]);
}
int main() {
scanf("%d",&n);
for (int i=1,opt,x;i<=n;i++) {
scanf("%d%d",&opt,&x);
if (opt==1) {
ins(rt,x);
} else if (opt==2) {
del(rt,x);
} else if (opt==3) {
printf("%d\n",rkf(rt,x)+1);
} else if (opt==4) {
printf("%d\n",kth(rt,x));
} else if (opt==5) {
printf("%d\n",pre(x));
} else {
printf("%d\n",nxt(x));
}
}
}
依旧是板子（代码就不放了），记得特判第一次 \(3,4,5,6\) 的操作。
标签：ch,return,浅谈,int,sizv,替罪羊,else,num From： https://www.cnblogs.com/NtYester/p/16783421.html