学习笔记_ 宗法树 线段平衡树 [学习笔记, 线段树, 平衡树, 数据结构]

一些奇怪的想法也许真的能成真

某毒瘤の线段平衡树

引言

这里写图片描述

我们知道平衡树…非常恶心…尤其旋转…容易把我这种沙茶选手转晕…

于是救世主ddd(ACM的主宰Orz)就隆重推出了一款 (某毒瘤传授的) 好懂又好写的神奇平衡树…我们命名为宗法树(具体命名原因下文会讲)

然而某毒瘤似乎不愿意我们叫她宗法树…他喜欢叫她线段平衡树或者finger tree…

大体思路

我们发现, 在一棵树上, 叶子节点是最好操作的: 删除的时候不用考虑拿那个节点旋转上来 思路比较简洁 那我们考虑只用叶子节点来存储信息

在宗法树中, 我们像线段树一样, 只用叶子存储具体的信息, 其他节点保存子树中的最大值和子树中的叶子节点数量

酱让我们看看怎么完成基本的BST操作:

e.g.1: luogu3369普通平衡树

  1. 插入x数: 直接从根找下去, 如果x比当前节点左子树里的最大值小, 递归到左子树里插入, 否则递归到右子树里插入, 直到一个空节点: 插入; 如果找到了一个叶子: 那么要新建两个节点, 来保证这棵树是一棵完全二叉树

  2. 删除x数(若有多个相同的数,因只删除一个): 从根找下去, 直到叶子节点, 直接删掉, (父节点的这个儿子设为NULL)

  3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名): 从根找下去…递归时向右儿子走一次就把答案加上他左兄弟包含的总叶子数量

  4. 查询排名为x的数: 从根找下去…递归时向右儿子走一回就把x减去他左兄弟的叶子节点值

  5. 求x的前驱(前驱定义为小于x,且最大的数): 直接查询x的排名, 查找kth(rank(x) - 1)

  6. 求x的后继(后继定义为大于x,且最小的数): 查询x + 1的排名, 查找kth(rank(x + 1))

一点解释:

  1. 插入的时候找到一个叶子节点要再新建一个节点保存那个叶子节点的值, 然后那个叶子节点就变为非叶子而且有两个儿子(一个刚插入的, 一个原来自己的值), 以保证只用叶子节点保存具体值
  2. 查询x的后继要查找在x + 1排名位置的数, 如果x未插入, 那么查找x的时候我们返回的是[如果x已经插入, x之后的节点], 所以如果x不在序列中, 我们直接返回的就是x的后继, 而查找x + 1是为了保证序列中正好有x的情况

以刚刚那个题的样例来说一下

luogu样例

蓝色是第一次插入, 发现根也是空的, 直接插入

绿色是第二次插入, 发现根是叶子, 复制了一个跟, 又把新来的317721插入到右儿子上, 更新根节点, 保存最大值(317721)

灰色是第三次插入…以此类推

旋转

别跑啊这个旋转可休闲了

我们发现啊这个e.g.1非常休闲啊, 不用旋转照样跑的比香港记者快啊废话 随机数据能不快嘛

我们拿着没有旋转的休闲平衡树写啊写 终于有一天碰到了一组毒瘤构造数据…我们的树变成了这个样…

GG辣

那个C, Y, K(也就是我T_T)代表很重的东西…也就是说这棵树树高差距很大了! 这时候复杂度最惨是 $O(n)$ 查询一次这怎么可以捏? 于是我们要旋转(别跑真的很休闲)…

其实他并没有转, 只是更改了一些连边关系, 于是变成了酱:

CYK被分开了

我们把很重的一坨东西从一个子树平衡到了另一个子树上, 完成了平衡…

但是! 人群之中跳出来一个毒瘤! 卡死了你的程序

如果一边实在是太重…而且重量集中在一边, 只旋转一次可能是不行的…

CYK偏沉了

那我们转两次…先在子树里平衡, 然后在当前的节点上平衡

没了 因为非叶子节点没有存储信息, 所以直接瞎连边就行

复杂度

时间复杂度无疑 $O(n\log_2n)$ , 旋转 $O(1)$, 插入, 删除, 各种查询都是 $O(树高)$, 平均一下也就是 $O(\log_2n)$

有人说空间复杂度很高??? 叶子一共$n$个还是二叉树你怎么高啊, 就是不垃圾回收也是 $O(n \lg n)$ 级别的…

空间?

我永远爱宗法树

一点不那么重要的东西

删除节点的时候是不是有点像父死子继兄终弟及…

旋转的时候是不是有点像是不是有点像过继…

于是…得名宗法树…然后又因为首字母原因被SLYZ人称为ZYF树 也就是开头那篇文章上的那个人

沙茶的 代码

几乎没有坑点啊! 代码非常简短啊! 对着板子打一遍就能30min打完啊!

而且功能很强啊! 资瓷合并啊! 某毒瘤说了吊打treap啊! 老娘还写什么treap啊(摔)! 我会告诉你我已经WA了一天的treap了嘛!

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXS (4)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7ffffff)
#define MNULL ((MAXN << 3) - 1)
using namespace std;
struct node
{
int maxz, ls, rs, sum;
node(): maxz(0), ls(MNULL), rs(MNULL), sum(0) {}
node(int zh, int l, int r, int s): maxz(zh), ls(l), rs(r), sum(s) {}
bool isLeaf()
{
return (ls == MNULL);
}
}b[MAXN << 3];
int root = MNULL, cnt;

inline int newnode(int, int, int, int);
void ins(int&, int);
void del(int, int, int);
int cxrk(int, int);
int cxkth(int, int);
inline void push_up(int);
inline void copynode(int, int);
int uni(int, int, int);
void rotate(int, bool);
void maintain(int);
int main(int argc, char const *argv[])
{
#define DEBUG
#ifdef DEBUG
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
switch(srx)
{
case 1: ins(root, sry); break;
case 2: del(root, root, sry); break;
case 3: printf("%d\n", cxrk(root, sry)); break;
case 4: printf("%d\n", cxkth(root, sry)); break;
case 5: printf("%d\n", cxkth(root, cxrk(root, sry) - 1)); break;
case 6: printf("%d\n", cxkth(root, cxrk(root, sry + 1))); break;
}
}
return 0;
}
inline int newnode(int zh, int ls, int rs, int sum)
{
b[++cnt] = node(zh, ls, rs, sum);
return cnt;
}
void ins(int& dq, int x)
{
if (dq == MNULL)
dq = newnode(x, MNULL, MNULL, 1);
else
{
if (b[dq].isLeaf())
{
b[dq].ls = newnode(min(b[dq].maxz, x), MNULL, MNULL, 1);
b[dq].rs = newnode(max(b[dq].maxz, x), MNULL, MNULL, 1);
}
else
{
if (x <= b[b[dq].ls].maxz)
ins(b[dq].ls, x);
else
ins(b[dq].rs, x);
}
}
maintain(dq);
push_up(dq);
}
inline void push_up(int dq)
{
if (!b[dq].isLeaf())
{
b[dq].sum = b[b[dq].ls].sum + b[b[dq].rs].sum;
b[dq].maxz = max(b[b[dq].ls].maxz, b[b[dq].rs].maxz);
}
}
void del(int dq, int fa, int x)
{
if (b[dq].isLeaf())
{
if (b[dq].maxz == x)
copynode(fa, ((b[fa].ls == dq) ? b[fa].rs : b[fa].ls));
return ;
}
if (x <= b[b[dq].ls].maxz)
del(b[dq].ls, dq, x);
else
del(b[dq].rs, dq, x);
maintain(dq);
push_up(dq);
}
int cxkth(int dq, int x) // 查询kth不要把maxz和sum写反...
{
if (b[dq].isLeaf())
return b[dq].maxz;
if (x <= b[b[dq].ls].sum)
return cxkth(b[dq].ls, x);
else
return cxkth(b[dq].rs, x - b[b[dq].ls].sum);
}
int cxrk(int dq, int x)
{
if (b[dq].isLeaf())
return ((b[dq].maxz < x) ? 2 : 1);
if (x <= b[b[dq].ls].maxz)
return cxrk(b[dq].ls, x);
else
return cxrk(b[dq].rs, x) + b[b[dq].ls].sum;
}
inline void copynode(int x, int y)
{
b[x].sum = b[y].sum;
b[x].maxz = b[y].maxz;
b[x].ls = b[y].ls;
b[x].rs = b[y].rs;
}
void maintain(int dq)
{
if (b[b[dq].ls].sum > b[b[dq].rs].sum * MAXS)
rotate(dq, true);
else if (b[b[dq].rs].sum > b[b[dq].ls].sum * MAXS)
rotate(dq, false);
if (b[b[dq].ls].sum > b[b[dq].rs].sum * MAXS)
rotate(b[dq].ls, false), rotate(dq, true);
else if (b[b[dq].rs].sum > b[b[dq].ls].sum * MAXS)
rotate(b[dq].rs, true), rotate(dq, false);
}
void rotate(int dq, bool isl)
{
if (!isl)
{
b[dq].ls = newnode(max(b[b[dq].ls].maxz, b[b[b[dq].rs].ls].maxz), b[dq].ls, b[b[dq].rs].ls, b[b[dq].ls].sum + b[b[b[dq].rs].ls].sum);
b[dq].rs = b[b[dq].rs].rs;
}
else
{
b[dq].rs = newnode(max(b[b[dq].rs].maxz, b[b[b[dq].ls].rs].maxz), b[b[dq].ls].rs, b[dq].rs, b[b[dq].rs].sum + b[b[b[dq].ls].rs].sum);
b[dq].ls = b[b[dq].ls].ls;
}
}