『学习笔记』fhq-treap
前言
修改（上锁）原因：有些地方忘打取地址惹%%%，还有Split里面的下标打成根的下标惹%%%
啥是平衡树
这边建议去这里。
分裂
一般指的是按值分裂，意思就是以树上的BST（二叉搜索树）的值为关键值分裂。一般会给一个关键值 \(val\) ，把一棵平衡树分裂成BST值 \(\leq val\) 和 \(> val\) 的两部分。
主要思想
从根开始递归，递归到某一节点，如果当前根节点的BST值小于等于你给的那个关键值，就往右子树递归，并且把刚才的根连到左子树根上；否则就往左子树递归，并且把刚才的根连到右子树根上。往哪边递归BST值相对大小关系决定的，而BST值又是由BST本身的性质决定的。
如果递归到叶子结点，需要把左右子树的根都清零！
代码实现
void Split(int p, int v, int& x, int& y) {
if (!p) {
x = y = 0;
return;
}
if (val[p] <= v) {
x = p;
Split(r[x], v, r[x], y); // bu shi [p]!!
Pushup(x); // fen bie geng xin liang ke zi shu de da xiao
}
else {
y = p;
Split(l[y], v, x, l[y]); // bu shi [p]!!
Pushup(y);
}
}
合并
一般只针对把两个分裂的平衡树（原来这两个平衡树是一个平衡树）合并到一个平衡树里（可以认为是分裂的逆操作）。因为是从一个平衡树分裂来的，所以它们谁是左子树谁是右子树就已经确定了，我们合并的时候就不用管谁左谁右，直接管谁上谁下即可。
主要思想
对于两个分裂的平衡树，我们从上往下递归地比较两个子树的根的heap值（就是随机值）的大小，谁小谁在上（默认小根堆），如果是左边的小，那就递归比较左根的右儿子和右根，否则递归比较左根和右根的左儿子。
如果一个非空根和另一个空根比较，直接返回那个非空根即可。
代码实现
// zhe wan yi zhang de gen xian duan shu he bing you dian xiang
int merge(int x, int y) { // 'x' zuo zi shu gen, 'y' you zi shu gen
if (!x || !y) return x | y;
if (rnk[x] < rnk[y]) {
r[x] = merge(r[x], y);
pushup(x);
return x; // bie wang le fan hui
}
else {
l[y] = merge(x, l[y]);
pushup(y);
return y;
}
}
插入一个BST值为 \(v\) 的点
主要思想
先把这个BST值为 \(v\) 点单独开出来作为一个新的平衡树，记为 \(\mathrm{z}\) ；然后再把现有的平衡树按照关键值 \(v\) 分裂为两个平衡树，分别记作 \(\mathrm{x}\) 和 \(\mathrm{y}\) 。先合并 \(\mathrm{x}\) 和 \(\mathrm{z}\) ，再合并 \(\mathrm{y}\) ，就能把这个点插进去。
不用担心如何有没有比较BST值相同但是heap值不同的两个点的heap值，因为它们在合并的时候就已经比较了。
如果插入的是一个序列，那么就先build一下，再合并即可。
代码实现
void Newnode(int& x, int v) {
x = ++tot;
val[x] = v;
rnk[x] = rand();
siz[x] = 1;
}
void Insert(int& p, int v) { // bie wang le &
int x, y, z;
Split(p, v, x, y);
Newnode(z, v);
p = Merge(Merge(x, z), y);
}
删除一个BST值为 \(v\) 的点
主要思想
把一棵平衡树分裂成BST值为 \([1, v - 1]\) 、 \(v\) 和 \([v + 1, max]\) 三部分，显然，BST值为 \(v\) 的平衡树是一条链，我们删去这条链的一个点，再把这三部分重新合并即可。
若我们记这条BST值大小为 \(v\) 的链（平衡树）为 \(\mathrm{y}\) ，则我们有操作：$$\mathrm{y} = merge(l[\mathrm{y}], r[\mathrm{y}])$$
这个平衡树不仅是链，而且还是一条向左的链，\(l[\mathrm{y}]\) 可能非空也可能空，\(r[\mathrm{y}]\) 一定空。所以将这两部分合并就相当于抛弃了根节点 \(\mathrm{y}\)。
代码实现
void Delete(int& p, int v) { // bie wang le &
int x, y, z, tmp;
Split(p, v, tmp, z);
Split(tmp, v - 1, x, y);
y = Merge(l[y], r[y]);
p = Merge(Merge(x, y), z);
}
已知权值 \(v\) 查排名 \(rnk\)
主要思想
把平衡树按 \(v - 1\) 分裂，记权值为 \([1, v - 1]\) 的为 \(\mathrm{x}\) ， \([v, max]\) 的为 \(\mathrm{y}\) 。即可得：$$rnk = siz[\mathrm{x}] + 1$$
代码实现
int getRankbyVal(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v - 1, x, y);
ans = siz[x] + 1;
p = Merge(x, y);
return ans;
}
已知排名查权值
主要思想
递归查找，如果左子树大小 \(+ 1\) 等于要查的排名，就直接返回根的权值。否则就递归查找，找哪边比较一下就行了。
代码实现
int getValbyRank(int p, int rnk) {
if (rnk == siz[l[p]] + 1) return val[p];
else if (rnk <= siz[l[p]]) {
return getValbyRank(l[p], rnk);
}
else {
return getValbyRank(r[p], rnk - siz[l[p]] - 1);
}
}
查 \(v\) 的前驱和后继
懒得打字了，直接粘我代码了。
代码实现
int getPre(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v - 1, x, y);
ans = getValbyRank(x, siz[x]);
p = Merge(x, y);
return ans;
}
int getNxt(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v, x, y);
ans = getValbyRank(y, 1);
p = Merge(x, y);
return ans;
}
总结
有啥好总结的，从前往后学明白了就啥都懂了，根本不用总结，然后就剩多打题了。
把我非常非常烂的板子粘上：
namespace FHQ_TREAP {
const int maxn = 100005;
int l[maxn], r[maxn];
int val[maxn], rnk[maxn];
int siz[maxn];
int tot = 0, root = 0;
class fhq_Treap {
public:
void Pushup(int p) {
siz[p] = siz[l[p]] + siz[r[p]] + 1; // bie wang le jia 1, yin wei hai you 'p' zi ji ben shen
}
void Split(int p, int v, int& x, int& y) {
if (!p) {
x = y = 0;
return;
}
if (val[p] <= v) {
x = p;
Split(r[x], v, r[x], y); // bu shi [p]!!
Pushup(x); // fen bie geng xin liang ke zi shu de da xiao
}
else {
y = p;
Split(l[y], v, x, l[y]); // bu shi [p]!!
Pushup(y);
}
}
// zhe wan yi zhang de gen xian duan shu he bing you dian xiang
int Merge(int x, int y) { // 'x' zuo zi shu gen, 'y' you zi shu gen
if (!x || !y) return x | y;
if (rnk[x] < rnk[y]) {
r[x] = Merge(r[x], y);
Pushup(x);
return x; // bie wang le fan hui
}
else {
l[y] = Merge(x, l[y]);
Pushup(y);
return y;
}
}
void Newnode(int& x, int v) {
x = ++tot;
val[x] = v;
rnk[x] = rand();
siz[x] = 1;
}
void Insert(int& p, int v) { // bie wang le &
int x, y, z;
Split(p, v, x, y);
Newnode(z, v);
p = Merge(Merge(x, z), y);
}
void Delete(int& p, int v) { // bie wang le &
int x, y, z, tmp;
Split(p, v, tmp, z);
Split(tmp, v - 1, x, y);
y = Merge(l[y], r[y]);
p = Merge(Merge(x, y), z);
}
int getRankbyVal(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v - 1, x, y);
ans = siz[x] + 1;
p = Merge(x, y);
return ans;
}
int getValbyRank(int p, int rnk) {
if (rnk == siz[l[p]] + 1) return val[p];
else if (rnk <= siz[l[p]]) {
return getValbyRank(l[p], rnk);
}
else {
return getValbyRank(r[p], rnk - siz[l[p]] - 1);
}
}
int getPre(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v - 1, x, y);
ans = getValbyRank(x, siz[x]);
p = Merge(x, y);
return ans;
}
int getNxt(int& p, int v) { // bie wang le &
int x, y, ans;
Split(p, v, x, y);
ans = getValbyRank(y, 1);
p = Merge(x, y);
return ans;
}
} T;
}
\