最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

「学习笔记」重修 FHQ-treap

来源：博客园

无旋 treap 的操作方式使得它天生支持维护序列、可持久化等特性。无旋 treap 又称分裂合并 treap。它仅有两种核心操作，即为 分裂与 合并。通过这两种操作，在很多情况下可以比旋转 treap 更方便的实现别的操作。

变量与宏定义

#define ls ch[u][0]#define rs ch[u][1]int cnt, rt, top;int ch[N][2], siz[N], val[N], pai[N], rub[N];

ls: 左孩子；rs: 右孩子；cnt: 计数器；rt: 根；top: “垃圾桶”的栈顶ch: 左右孩子，0为左孩子，1为右孩子；siz: 子树大小；val: 键值；pai：随机的值，用于堆排序；rub: 垃圾桶。


(相关资料图)

操作

  • 按权值分裂

给定一个权值，小于等于该权值的分裂到左边，大于该权值的分裂到右边。在分裂过程中也要维护二叉搜索树的性质，即当前节点左子树任意一个节点的 val都小于等于当前节点的 val，右子树任意一个节点的 val都大于当前节点的 val。

void split1(int u, int c, int &x, int &y) { // 按照权值分裂if (u == 0) {x = y = 0;return ;}if (val[u] <= c) {x = u;split1(rs, c, rs, y);}else {y = u;split1(ls, c, x, ls);}pushup(u);}

u: 当前节点；c: 给定分裂的权值；x: 要分裂成的左树；y: 要分裂成的右树。

if (val[u] <= v) {x = u;split1(rs, c, rs, y);}

如果当前节点的 val小于 \(c\)，那么久把当前节点连带它的左子树一起放到 x上，接下来向右子树搜索，若还有要接到 x上的节点，就接到 x的右子树上，以此来维护二叉搜索树的性质。如下图（图片来自 \(\text{OI wiki}\)）。pushup(u);为更新函数，后面会写。

  • 按子树大小分裂

将前 \(k\) 个节点分成一棵树，其他节点分成一棵树。

void split2(int u, int k, int &x, int &y) { // 按照子树大小分裂if (u == 0) {x = y = 0;return ;}pushup(u);if (siz[ls] + 1 <= k) {x = u;split2(rs, k - siz[ls] - 1, rs, y);}else {y = u;split2(ls, k, x, ls);}pushup(u);}
if (siz[ls] + 1 <= k) {x = u;split2(rs, k - siz[ls] - 1, rs, y);}

siz[ls] + 1是当前的节点和它的左子树的总 siz，siz小于 \(k\)，放到左子树，x变成 rs。

  • 合并

两棵树合并，如果一棵树为空，则直接合并，否则，根据 pai的大小来判断谁是父节点。小根堆 pai小的为父节点，大根堆 pai大的为父节点。

int merge(int x, int y) {if (!x || !y) {return x + y;}if (pai[x] < pai[y]) {ch[x][1] = merge(ch[x][1], y);pushup(x);return x;}else {ch[y][0] = merge(x, ch[y][0]);pushup(y);return y;}}

注意，合并时 x是左树，y是右树，一定要保证左右顺序！

  • 更新信息

void pushup(int u) {siz[u] = siz[ls] + siz[rs] + 1;return ;}

  • 删除节点

这里是删除已知权值的点，若存在多个则只删一个，删除的点将放进“垃圾桶”，当有些节点要创建时先从“垃圾桶”里找可用的点，节省空间。

void del(int c) {int t1, t2, t3;split1(rt, c, t1, t2);split1(t1, c - 1, t1, t3);rub[++ top] = t3;t3 = merge(ch[t3][0], ch[t3][1]);rt = merge(merge(t1, t3), t2);}
t3 = merge(ch[t3][0], ch[t3][1]);rt = merge(merge(t1, t3), t2);

由于相同权值的节点只删了一个，t3可能不为空，所以还要再合并起来.

  • 创建新节点

int New(int c) {int u;if (!top) {u = ++ cnt;}else {u = rub[top];top --;}val[u] = c;siz[u] = 1;pai[u] = rand();ls = 0, rs = 0;return u;}
if (!top) {u = ++ cnt;}else {u = rub[top];top --;}

如果“垃圾桶”里还有点，那就将这些点回收利用，否则就开新节点。

  • 插入

先将树按照权值分裂，然后将新节点依次与左树和右树合并，merge的顺序不要搞反了。

void insert(int c) {int t1, t2;split1(rt, c, t1, t2);rt = merge(merge(t1, New(c)), t2);}

  • 查询排名

按照权值分裂，返回 siz[ls] + 1。

int ranking(int c) {int t1, t2, k;split1(rt, c - 1, t1, t2);k = siz[t1] + 1;rt = merge(t1, t2);return k;}

  • 查询第 \(K\) 大

按照子树大小分裂即可

int K_th(int k) {int t1, t2, t3, c;split2(rt, k, t1, t2);split2(t1, k - 1, t1, t3);c = val[t3];rt = merge(merge(t1, t3), t2);return c;}

  • 查找前驱

int pre(int c) {int t1, t2, t3, k;split1(rt, c - 1, t1, t2);split2(t1, siz[t1] - 1, t1, t3);k = val[t3];rt = merge(merge(t1, t3), t2);return k;}

  • 查找后继

int nxt(int c) {int t1, t2, t3, k;split1(rt, c, t1, t2);split2(t2, 1, t2, t3);k = val[t2];rt = merge(t1, merge(t2, t3));return k;}

由于 FHQ 的核心操作是分裂与合并，所以，不同于 treap，它可以方便的进行区间操作。

模板

struct FHQ {int cnt, rt, top;int ch[N][2], siz[N], val[N], pai[N], rub[N];void pushup(int u) {siz[u] = siz[ls] + siz[rs] + 1;return ;}int New(int c) {int u;if (!top) {u = ++ cnt;}else {u = rub[top];top --;}val[u] = c;siz[u] = 1;pai[u] = rand();ls = 0, rs = 0;return u;}void split1(int u, int c, int &x, int &y) { // 按照权值分裂if (u == 0) {x = y = 0;return ;}if (val[u] <= c) {x = u;split1(rs, c, rs, y);}else {y = u;split1(ls, c, x, ls);}pushup(u);}void split2(int u, int k, int &x, int &y) { // 按照子树大小分裂if (u == 0) {x = y = 0;return ;}pushup(u);if (siz[ls] + 1 <= k) {x = u;split2(rs, k - siz[ls] - 1, rs, y);}else {y = u;split2(ls, k, x, ls);}pushup(u);}int merge(int x, int y) {if (!x || !y) {return x + y;}if (pai[x] < pai[y]) {ch[x][1] = merge(ch[x][1], y);pushup(x);return x;}else {ch[y][0] = merge(x, ch[y][0]);pushup(y);return y;}}void insert(int c) {int t1, t2;split1(rt, c, t1, t2);rt = merge(merge(t1, New(c)), t2);}void del(int c) {int t1, t2, t3;split1(rt, c, t1, t2);split1(t1, c - 1, t1, t3);rub[++ top] = t3;t3 = merge(ch[t3][0], ch[t3][1]);rt = merge(merge(t1, t3), t2);}int ranking(int c) {int t1, t2, k;split1(rt, c - 1, t1, t2);k = siz[t1] + 1;rt = merge(t1, t2);return k;}int K_th(int k) {int t1, t2, t3, c;split2(rt, k, t1, t2);split2(t1, k - 1, t1, t3);c = val[t3];rt = merge(merge(t1, t3), t2);return c;}int pre(int c) {int t1, t2, t3, k;split1(rt, c - 1, t1, t2);split2(t1, siz[t1] - 1, t1, t3);k = val[t3];rt = merge(merge(t1, t3), t2);return k;}int nxt(int c) {int t1, t2, t3, k;split1(rt, c, t1, t2);split2(t2, 1, t2, t3);k = val[t2];rt = merge(t1, merge(t2, t3));return k;}};

关键词：