Ntの咖啡馆
0%

浅谈替罪羊树

发表于 更新于

前言

噫，好！我又来了

这几天闲着没事翻桃片，发现好多人卡评测被封了，就看了看紫荆花，发现 splay 会被卡，就去学了替罪羊树（$\text{Scapegoat Tree}$）。

正文

写在前面

大家都知道，splay 是通过旋转维护整棵树的平衡，但也会出现深度过大而导致复杂度爆炸的情况。

而替罪羊树则是通过重构来维护平衡，他会初始一个失衡系数 $\alpha$，一般取 $[0.7,0.8]$，然后通过比较左右子树大小和自身大小来判断是否失衡，若失衡，就拍扁重构

然后是关于删除的一个问题，替罪羊树用的是惰性删除（把当前节点个数清零，但不从树中删去），记住这个东西，对之后的很多东西是都有影响的。

关于结构体

1
2
3
struct Node {
	int val,num,ch[2],sizt,sizv,siznd;
}t[2000001];

可以发现，基本上与 splay 没有什么太大区别，但多了，三个 siz 并且没有 fa（因为他不需要遍历父亲）。

解读一下这三个 siz。

  1. sizt：子树中有多少个不同的权值（包括空节点）

  2. sizv：子树中有多少个节点（不包括空节点）

  3. siznd：子树中有多少个不同的权值（不包括空节点）

对应的 upd 应该这么写

1
2
3
4
5
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);
}

关于重构

就是把一棵树展开进一个线性表中，再二分建树（空节点不建树），比较简单，直接上代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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); }

判断是否重构有三个条件

  1. 本节点是否为空

  2. 自己的 sizt 乘上 $\alpha$ 是否小于左右子树中最大的子树的 sizt

  3. 自己的 sizt 乘上 $\alpha$ 是否大于自己的 siznd

关于第三条，因为惰性删除，删除操作一旦过多，会导致树中的空节点过多，显而易见，空节点多没有用，所以，可通过重构操作删去。

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))); }

查询排名

替罪羊树有两个函数，一个为 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，所以要往左子树搜。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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{本节点}}]$ 即可，如果小往左子树搜，大则往右子树搜。

1
2
3
4
5
6
7
8
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);
	}
}

前驱以及后继

结合一下上面的三个函数即可。

1
2
3
int pre(int x) { return kth(rt,rkf(rt,x)); }

int nxt(int x) { return kth(rt,rkl(rt,x)); }

插入

比较简单，递归插入即可，不多说了。

回溯时记得重构。

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
	}
}

删除

同上

1
2
3
4
5
6
7
8
9
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%$ 会咕。

【模板】普通平衡树

板子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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$ 的操作。