差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:splay [2020/08/22 16:03]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:splay [2020/08/22 22:11] (当前版本)
lgwza [删除操作]
@@ 行 45: / 行 45: @@
 在 $\text{Splay}$ 中旋转分为两种：左旋和右旋。
-{{E:\ACM\学习笔记\数据结构\splay2.png| splay2}}
+{{https://oi-wiki.org/ds/images/splay2.png|Splay2}}
+**具体分析旋转步骤**（假设需要旋转的结点为 $x$，其父亲为 $y$，以右旋为例）
+  - 将 $y$ 的左儿子指向 $x$ 的右儿子，且 $x$ 的右儿子的父亲指向 $y$。''%%ch[y][0]=ch[x][1];fa[ch[x][1]]=y;%%''
+  - 将 $x$ 的右儿子指向 $y$，且 $y$ 的父亲指向 $x$。''%%ch[x][chk^1]=y;fa[y]=x;%%''
+  - 如果原来的 $y$ 还有父亲 $z$，那么把 $z$ 的某个儿子（原来 $y$ 所在的儿子位置）指向 $x$，且 $x$ 的父亲指向 $z$。''%%fa[x]=z;if(z) ch[z][y==ch[z][1]]=x;%%''
+<code cpp>
+void rotate(int x) {
+  int y = fa[x], z = fa[y], chk = get(x);
+  ch[y][chk] = ch[x][chk ^ 1];
+  fa[ch[x][chk ^ 1]] = y;
+  ch[x][chk ^ 1] = y;
+  fa[y] = x;
+  fa[x] = z;
+  if (z) ch[z][y == ch[z][1]] = x;
+  maintain(y);
+  maintain(x);
+}
+</code>
+==== Splay 操作 ====
+$\text{Splay}$ 规定：每访问一个结点后都要强制将其旋转到根结点。此时旋转操作具体分为 $6$ 种情况讨论（其中 $x$ 为需要旋转到根的结点）
+{{https://oi-wiki.org/ds/images/splay1.png| img}}
+  * 如果 $x$ 的父亲是根结点，直接将 $x$ 左旋或右旋（图 $1,2$）。
+  * 如果 $x$ 的父亲不是根结点，且 $x$ 和父亲的儿子类型相同，首先将其父亲左旋或右旋，然后将 $x$ 右旋或左旋（图 $3,4$）。
+  * 如果 $x$ 的父亲不是根结点，且 $x$ 和父亲的儿子类型不同，将 $x$ 左旋再右旋、或者右旋再左旋（图 $5,6$）。
+分析起来一大串，其实代码一小段。大家可以自己模拟一下 $6$ 种旋转情况，就能理解 $\text{Splay}$ 的基本思想了。
+<code cpp>
+void splay(int x) {
+  for (int f = fa[x]; f = fa[x], f; rotate(x))
+    if (fa[f]) rotate(get(x) == get(f) ? f : x);
+  rt = x;
+}
+</code>
+==== 插入操作 ====
+插入操作是一个比较复杂的过程，具体步骤如下（插入的值为 $k$）：
+  * 如果树空了则直接插入根并退出。
+  * 如果当前结点的权值等于 $k$ 则增加当前结点的大小并更新结点和父亲的信息，将当前结点进行 $\text{Splay}$ 操作。
+  * 否则按照二叉查找树的性质向下找，找到空结点就插入即可（当然别忘了 $\text{Splay}$ 操作）。
+<code cpp>
+void ins(int k) {
+  if (!rt) {
+    val[++tot] = k;
+    cnt[tot]++;
+    rt = tot;
+    maintain(rt);
+    return;
+  }
+  int cnr = rt, f = 0;
+  while (1) {
+    if (val[cnr] == k) {
+      cnt[cnr]++;
+      maintain(cnr);
+      maintain(f);
+      splay(cnr);
+      break;
+    }
+    f = cnr;
+    cnr = ch[cnr][val[cnr] < k];
+    if (!cnr) {
+      val[++tot] = k;
+      cnt[tot]++;
+      fa[tot] = f;
+      ch[f][val[f] < k] = tot;
+      maintain(tot);
+      maintain(f);
+      splay(tot);
+      break;
+    }
+  }
+}
+</code>
+==== 查询 x 的排名 ====
+根据二叉查找树的定义和性质，显然可以按照以下步骤查询 $x$ 的排名：
+  * 如果 $x$ 比当前结点权值小，向其左子树查找。
+  * 如果 $x$ 比当前结点权值大，将答案加上左子树（$size$）和当前结点（$cnt$）的大小，向其右子树查找。
+  * 如果 $x$ 与当前结点的权值相同，将答案加 $1$ 并返回。
+注意最后需要进行 $\text{Splay}$ 操作。
+<code cpp>
+int rk(int k) {
+  int res = 0, cnr = rt;
+  while (1) {
+    if (k < val[cnr]) {
+      cnr = ch[cnr][0];
+    } else {
+      res += sz[ch[cnr][0]];
+      if (k == val[cnr]) {
+        splay(cnr);
+        return res + 1;
+      }
+      res += cnt[cnr];
+      cnr = ch[cnr][1];
+    }
+  }
+}
+</code>
+==== 查询排名 x 的数 ====
+设 $k$ 为剩余排名，具体步骤如下：
+  * 如果左子树非空且剩余排名 $k$ 不大于左子树的大小 $size$，那么向左子树查找。
+  * 否则将 $k$ 减去左子树和根的大小。如果此时 $k$ 的值小于等于 $0$，则返回根结点的权值，否则继续向右子树查找。
+<code cpp>
+int kth(int k) {
+  int cnr = rt;
+  while (1) {
+    if (ch[cnr][0] && k <= sz[ch[cnr][0]]) {
+      cnr = ch[cnr][0];
+    } else {
+      k -= cnt[cnr] + sz[ch[cnr][0]];
+      if (k <= 0) {
+        splay(cnr);
+        return val[cnr];
+      }
+      cnr = ch[cnr][1];
+    }
+  }
+}
+</code>
+==== 查询前驱 ====
+前驱定义为小于 $x$ 的最大的数，那么查询前驱可以转化为：将 $x$ 插入（此时 $x$ 已经在根的位置了），前驱即为 $x$ 的左子树中最右边的结点，最后将 $x$ 删除即可。
+<code cpp>
+int pre() {
+  int cnr = ch[rt][0];
+  while (ch[cnr][1]) cnr = ch[cnr][1];
+  splay(cnr);
+  return cnr;
+}
+</code>
+==== 查询后继 ====
+后继定义为大于 $x$ 的最小的数，查询方法和前驱类似：$x$ 的右子树中最左边的结点。
+<code cpp>
+int nxt() {
+  int cnr = ch[rt][1];
+  while (ch[cnr][0]) cnr = ch[cnr][0];
+  splay(cnr);
+  return cnr;
+}
+</code>
+==== 合并两棵树 ====
+合并两棵 Splay 树，设两棵树的根结点分别为 $x$ 和 $y$，那么我们要求 $x$ 树中的最大值小于 $y$ 树中的最小值。合并操作如下：
+  * 如果 $x$ 和 $y$ 其中之一或两者都为空树，直接返回不为空的那一棵树的根结点或空树。
+  * 否则将 $x$ 树中的最大值 $\text{Splay}$ 到根，然后把它的右子树设置为 $y$ 并更新结点的信息，然后返回这个结点。
+==== 删除操作 ====
+删除操作也是一个比较复杂的操作，具体步骤如下：
+首先将 $x$ 旋转到根的位置。
+  * 如果 $cnt[x]>1$（有不止一个 $x$），那么将 $cnt[x]$ 减 $1$ 并退出。
+  * 否则，合并它的左右两棵子树即可。
+<code cpp>
+void del(int k) {
+  rk(k);
+  if (cnt[rt] > 1) {
+    cnt[rt]--;
+    maintain(rt);
+    return;
+  }
+  if (!ch[rt][0] && !ch[rt][1]) {
+    clear(rt);
+    rt = 0;
+    return;
+  }
+  if (!ch[rt][0]) {
+    int cnr = rt;
+    rt = ch[rt][1];
+    fa[rt] = 0;
+    clear(cnr);
+    return;
+  }
+  if (!ch[rt][1]) {
+    int cnr = rt;
+    rt = ch[rt][0];
+    fa[rt] = 0;
+    clear(cnr);
+    return;
+  }
+  int cnr = rt, x = pre();
+  splay(x);
+  fa[ch[cnr][1]] = x;
+  ch[x][1] = ch[cnr][1];
+  clear(cnr);
+  maintain(rt);
+}
+</code>
+===== 完整代码 =====
+<hidden>
+<code cpp>
+#include <cstdio>
+const int N = 100005;
+int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];
+struct Splay {
+  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }
+  bool get(int x) { return x == ch[fa[x]][1]; }
+  void clear(int x) {
+    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
+  }
+  void rotate(int x) {
+    int y = fa[x], z = fa[y], chk = get(x);
+    ch[y][chk] = ch[x][chk ^ 1];
+    fa[ch[x][chk ^ 1]] = y;
+    ch[x][chk ^ 1] = y;
+    fa[y] = x;
+    fa[x] = z;
+    if (z) ch[z][y == ch[z][1]] = x;
+    maintain(x);
+    maintain(y);
+  }
+  void splay(int x) {
+    for (int f = fa[x]; f = fa[x], f; rotate(x))
+      if (fa[f]) rotate(get(x) == get(f) ? f : x);
+    rt = x;
+  }
+  void ins(int k) {
+    if (!rt) {
+      val[++tot] = k;
+      cnt[tot]++;
+      rt = tot;
+      maintain(rt);
+      return;
+    }
+    int cnr = rt, f = 0;
+    while (1) {
+      if (val[cnr] == k) {
+        cnt[cnr]++;
+        maintain(cnr);
+        maintain(f);
+        splay(cnr);
+        break;
+      }
+      f = cnr;
+      cnr = ch[cnr][val[cnr] < k];
+      if (!cnr) {
+        val[++tot] = k;
+        cnt[tot]++;
+        fa[tot] = f;
+        ch[f][val[f] < k] = tot;
+        maintain(tot);
+        maintain(f);
+        splay(tot);
+        break;
+      }
+    }
+  }
+  int rk(int k) {
+    int res = 0, cnr = rt;
+    while (1) {
+      if (k < val[cnr]) {
+        cnr = ch[cnr][0];
+      } else {
+        res += sz[ch[cnr][0]];
+        if (k == val[cnr]) {
+          splay(cnr);
+          return res + 1;
+        }
+        res += cnt[cnr];
+        cnr = ch[cnr][1];
+      }
+    }
+  }
+  int kth(int k) {
+    int cnr = rt;
+    while (1) {
+      if (ch[cnr][0] && k <= sz[ch[cnr][0]]) {
+        cnr = ch[cnr][0];
+      } else {
+        k -= cnt[cnr] + sz[ch[cnr][0]];
+        if (k <= 0) {
+          splay(cnr);
+          return val[cnr];
+        }
+        cnr = ch[cnr][1];
+      }
+    }
+  }
+  int pre() {
+    int cnr = ch[rt][0];
+    while (ch[cnr][1]) cnr = ch[cnr][1];
+    splay(cnr);
+    return cnr;
+  }
+  int nxt() {
+    int cnr = ch[rt][1];
+    while (ch[cnr][0]) cnr = ch[cnr][0];
+    splay(cnr);
+    return cnr;
+  }
+  void del(int k) {
+    rk(k);
+    if (cnt[rt] > 1) {
+      cnt[rt]--;
+      maintain(rt);
+      return;
+    }
+    if (!ch[rt][0] && !ch[rt][1]) {
+      clear(rt);
+      rt = 0;
+      return;
+    }
+    if (!ch[rt][0]) {
+      int cnr = rt;
+      rt = ch[rt][1];
+      fa[rt] = 0;
+      clear(cnr);
+      return;
+    }
+    if (!ch[rt][1]) {
+      int cnr = rt;
+      rt = ch[rt][0];
+      fa[rt] = 0;
+      clear(cnr);
+      return;
+    }
+    int cnr = rt;
+    int x = pre();
+    splay(x);
+    fa[ch[cnr][1]] = x;
+    ch[x][1] = ch[cnr][1];
+    clear(cnr);
+    maintain(rt);
+  }
+} tree;
+int main() {
+  int n, opt, x;
+  for (scanf("%d", &n); n; --n) {
+    scanf("%d%d", &opt, &x);
+    if (opt == 1)
+      tree.ins(x);
+    else if (opt == 2)
+      tree.del(x);
+    else if (opt == 3)
+      printf("%d\n", tree.rk(x));
+    else if (opt == 4)
+      prin
+</code>
+</hidden>
+===== 例题 =====
+以下题目都是裸的 $\text{Splay}$ 维护二叉查找树。
+[[https://loj.ac/problem/104|【模板】普通平衡树]]
+[[https://loj.ac/problem/105|【模板】文艺平衡树]]
+[[https://loj.ac/problem/10143|「HNOI2002」营业额统计]]
+[[https://loj.ac/problem/10144|「HNOI2004」宠物收养所]]
+===== 练习题 =====
+[[https://www.luogu.com.cn/problem/P4402|「Cerc2007」robotic sort 机械排序]]
+[[https://loj.ac/problem/106|二逼平衡树（树套树）]]
+[[http://www.lydsy.com/JudgeOnline/problem.php?id=2827|bzoj 2827 千山鸟飞绝]]
+[[http://www.lydsy.com/JudgeOnline/problem.php?id=4923|「Lydsy1706 月赛」K 小值查询]]
+===== 参考链接 =====
+[[https://oi-wiki.org/ds/splay/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具