核心：不管是插入还是查询，都会将待操作数splay到树根。
可以证明：无论在何种数据下，使用splay操作，都能保证平均意义下O(logn)的时间复杂度。

数据结构

  1. static class Node {
  2.     int[] s = new int[2];    // 子节点
  3.     int p;                    // 父节点
  4.     int v;                    // 节点维护的数据信息
  5.     int size, flag;            // 以当前节点为根的子树的总节点数，懒标记
  6. }
  8. static final int N = 100010;
  9. static Node[] tr = new Node[N];
  10. static int root, idx;
  12. static void splay(int x, int k);     // 伸展操作
  13. static void rotate(int x);            // 旋转操作
  14. static void insert(int v);            // 插入值为v的节点
  15. static void delete(int v);            // 删除值为v的节点
  16. static void delete(int vl, int vr);    // 删除值为[vl, vr]的一段节点
  17. static void pushup(int x);            // 向上更新
  18. static void pushdown(int x);        // 向下更新
  19. static int get_r(int k);            // 获取中序遍历的第k个数（不一定是第k大）
  20. static void output(int u);            // 中序遍历输出整棵树

splay操作

splay(x, k)将x指向的节点旋转至k节点下方。
分两种情况：

  1. 第一种：直线型
  2.         z                y                x
  3.        /               / \                 \
  4.       y            =>    x      z    =>              z
  5.      /                                           \
  6.     x                                        y
  8. 第二种：折线型    
  10.         z                z                x
  11.        /               /               /  \
  12.       y            =>      x            =>      y       z
  13.        \             /
  14.          x            y

作用：将x节点转至k点下方，并使树更平衡

  1. static void splay(int x, int k) {
  2.     while (tr[x].p != k) {
  3.         int y = tr[x].p, z = tr[y].p;
  4.         if (z != k)
  5.             if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))
  6.                 rotate(x);
  7.         else rotate(y);
  8.         rotate(x);
  9.     }
  10.     if (k == 0) root = x;
  11. }

rotate操作

  1. static void rotate(int x) {
  2.     int y = tr[x].p, z = tr[y].p;
  3.     int k = tr[y].s[1] == x ? 1 : 0;
  4.     tr[z].s[tr[z].s[1] == y ? 1 : 0] = x;
  5.     tr[x].p = z;
  6.     tr[y].s[k] = tr[x].s[k ^ 1];
  7.     tr[tr[x].s[k ^ 1]].p = y;
  8.     tr[x].s[k ^ 1] = y;
  9.     tr[y].p = x;
  10.     pushup(y);
  11.     pushup(x);
  12. }

insert操作

插入值为v的节点

  1. static void insert(int v) {
  2.     int u = root, p = 0;
  3.     while (u != 0) {
  4.         p = u;
  5.         u = v > tr[u].v ? tr[u].s[1] : tr[u].s[0];
  6.     }
  7.     u = ++idx;
  8.     tr[u] = new Node(v, p);
  9.     if (p != 0) tr[p].s[tr[p].v > v ? 0 : 1] = u;
  10.     splay(u, 0);
  11. }

delete操作

pushup操作

在rotate结尾调用

  1. static void pushup(int x) {
  2.     tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
  3. }

pushdown操作

在output和get_r开始调用，即递归操作的开始调用

  1. static void pushdown(int x) {
  2.     if (tr[x].flag == 1) {
  3.         swap(x);
  4.         tr[tr[x].s[0]].flag ^= 1;
  5.         tr[tr[x].s[1]].flag ^= 1;
  6.         tr[x].flag = 0;
  7.     }
  8. }
  9. static void swap(int x) {
  10.     int t = tr[x].s[0];
  11.     tr[x].s[0] = tr[x].s[1];
  12.     tr[x].s[1] = t;
  13. }

get_r操作

获取第k个节点

  1. static int get_r(int k) {
  2.     int u = root;
  3.     while (u != 0) {
  4.         pushdown(u);
  5.         if (tr[tr[u].s[0]].size + 1 < k) {
  6.             k -= tr[tr[u].s[0]].size + 1;
  7.             u = tr[u].s[1];
  8.         } else if (tr[tr[u].s[0]].size + 1 == k) {
  9.             return u;
  10.         } else u = tr[u].s[0];
  11.     }
  12.     return -1;
  13. }

output操作

输出整棵树的中序遍历结果

  1. static void output(int u) {
  2.     pushdown(u);
  3.     if (tr[u].s[0] != 0)
  4.         output(tr[u].s[0]);
  5.     if (tr[u].v >= 1 && tr[u].v <= n)
  6.         System.out.print(tr[u].v + " ");
  7.     if (tr[u].s[1] != 0)
  8.         output(tr[u].s[1]);
  9. }

例题

Acwing 2437. Splay模板题

给定一个长度为 nn 的整数序列，初始时序列为 {1,2,…,n−1,n}。
序列中的位置从左到右依次标号为 1∼n。
我们用 [l,r] 来表示从位置 l 到位置 r 之间（包括两端点）的所有数字构成的子序列。
现在要对该序列进行 m 次操作，每次操作选定一个子序列 [l,r]，并将该子序列中的所有数字进行翻转。
例如，对于现有序列 1 3 2 4 6 5 7，如果某次操作选定翻转子序列为 [3,6]，那么经过这次操作后序列变为 1 3 5 6 4 2 7。
请你求出经过 m 次操作后的序列。
输入格式
第一行包含两个整数 n,m。
接下来 m 行，每行包含两个整数 l,r，用来描述一次操作。
输出格式
共一行，输出经过 m 次操作后的序列。
数据范围
1≤n,m≤105,
1≤l≤r≤n
输入样例：
6 3 2 4 1 5 3 5
输出样例：
5 2 1 4 3 6

  1. import java.util.*;
  3. public class Main {
  4.     static class Node {
  5.         int[] s = new int[2];
  6.         int v, p;
  7.         int size, flag;
  8.         Node(int v, int p) {
  9.             this.v = v;
  10.             this.p = p;
  11.         }
  12.     }
  14.     static final int N = 100010;
  15.     static Node[] tr = new Node[N];
  16.     static int n, m, idx, root;
  17.     public static void main(String[] args) {
  18.         Scanner sc = new Scanner(System.in);
  19.         n = sc.nextInt();
  20.         m = sc.nextInt();
  21.         tr[0] = new Node(0, 0);
  22.         for (int i = 0; i <= n + 1; i++)
  23.             insert(i);
  24.         while (m-- > 0) {
  25.             int l = sc.nextInt(), r = sc.nextInt();
  26.             l = get_r(l);
  27.             r = get_r(r + 2);
  28.             splay(l, 0);
  29.             splay(r, l);
  30.             tr[tr[r].s[0]].flag ^= 1;
  31.         }
  32.         output(root);
  33.     }
  34.     static void insert(int v) {
  35.         int u = root, p = 0;
  36.         while (u != 0) {
  37.             p = u;
  38.             u = v > tr[u].v ? tr[u].s[1] : tr[u].s[0];
  39.         }
  40.         u = ++idx;
  41.         tr[u] = new Node(v, p);
  42.         if (p != 0) tr[p].s[tr[p].v > v ? 0 : 1] = u;
  43.         splay(u, 0);
  44.     }
  46.     static void splay(int x, int k) {
  47.         while (tr[x].p != k) {
  48.             int y = tr[x].p, z = tr[y].p;
  49.             if (z != k)
  50.                 if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))
  51.                     rotate(x);
  52.                 else rotate(y);
  53.             rotate(x);
  54.         }
  55.         if (k == 0) root = x;
  56.     }
  58.     static void rotate(int x) {
  59.         int y = tr[x].p, z = tr[y].p;
  60.         int k = tr[y].s[1] == x ? 1 : 0;
  61.         tr[z].s[tr[z].s[1] == y ? 1 : 0] = x;
  62.         tr[x].p = z;
  63.         tr[y].s[k] = tr[x].s[k ^ 1];
  64.         tr[tr[x].s[k ^ 1]].p = y;
  65.         tr[x].s[k ^ 1] = y;
  66.         tr[y].p = x;
  67.         pushup(y);
  68.         pushup(x);
  69.     }
  71.     static void pushup(int x) {
  72.         tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
  73.     }
  74.     static void pushdown(int x) {
  75.         if (tr[x].flag == 1) {
  76.             swap(x);
  77.             tr[tr[x].s[0]].flag ^= 1;
  78.             tr[tr[x].s[1]].flag ^= 1;
  79.             tr[x].flag = 0;
  80.         }
  81.     }
  82.     static void swap(int x) {
  83.         int t = tr[x].s[0];
  84.         tr[x].s[0] = tr[x].s[1];
  85.         tr[x].s[1] = t;
  86.     }
  88.     static int get_r(int k) {
  89.         int u = root;
  90.         while (u != 0) {
  91.             pushdown(u);
  92.             if (tr[tr[u].s[0]].size + 1 < k) {
  93.                 k -= tr[tr[u].s[0]].size + 1;
  94.                 u = tr[u].s[1];
  95.             } else if (tr[tr[u].s[0]].size + 1 == k) {
  96.                 return u;
  97.             } else u = tr[u].s[0];
  98.         }
  99.         return -1;
  100.     }
  102.     static void output(int u) {
  103.         pushdown(u);
  104.         if (tr[u].s[0] != 0)
  105.             output(tr[u].s[0]);
  106.         if (tr[u].v >= 1 && tr[u].v <= n)
  107.             System.out.print(tr[u].v + " ");
  108.         if (tr[u].s[1] != 0)
  109.             output(tr[u].s[1]);
  110.     }
  111. }