结构定义Splay Structure#

与前两个数据结构都不同的是， 多维护了一项“父节点”的信息。因为在伸展树操作过程中，会涉及到将节点向树根转动的操作，这时记录一个父节点就显得非常有必要且方便的了。其余内容和普通的平衡树就相差无几了：

1
struct Splay {
2
    int s[2];   // 0 for left son, 1 for right son
3
    int p;      // Father node index
4
    int dat;    // Value
5
    int cnt;    // Duplication count
6
    int size;   // Node count in total
7
} tree[N];

再谈旋转Zigzagging Pt.II#

在平衡树 2.3节中，我们探讨了平衡树中左旋右旋的基本规则，并给出了三种简记技巧。在 中，我们需要对平衡树的旋转操作进行一个更加深入的探讨。

可以发现，左旋和右旋是互为相反操作的。事实上，我们可以把整个旋转操作写成一个函数，通过传参来执行不同类型的旋转。我们只需要指定旋转的节点，至于旋转的取向则由程序自行决定（正确性是有保障的）。我们可以先分别写出左旋和右旋的函数，然后再把它们组合起来，最后别忘了更新父节点、以及上传子树大小（注意代码顺序）：

1
void rotate(int x) {
2
    int y = tree[x].p, z = tree[y].p;           // Father and grandfather
3
    int sn_pos = (tree[y].s[1] == x);           // Where the son is, 0 left, 1 right
4
    int fa_pos = (tree[z].s[1] == y);           // Where the father is, 0 left, 1 right
5
    tree[z].s[fa_pos] = x;                      // Son and father need a swap. If father was on the left previously, the son will be placed as a father on the left
6
    tree[x].p = z;                              // Update father 1
7
    tree[y].s[sn_pos] = tree[x].s[sn_pos ^ 1];  // In the mid-traversal order, node B is between X and Y, so it will be linked to the opposite side
8
    tree[tree[x].s[sn_pos ^ 1]].p = y;          // Update father 2
9
    tree[x].s[sn_pos ^ 1] = y;                  // After a round of zigzagging, left branch that connects father and son will be switched to the right side
10
    tree[y].p = x;                              // Update father 3
11
    update(y);
12
    update(x);
13
}

树的伸展To Splay in Splay#

伸展树的灵魂与核心就在于它可以将任意节点转动到其他节点下面去，这一操作就叫做“伸展Splay”。在 中，每次对节点进行一次操作，就需要把它转动到根节点下面去。虽然听起来很玄学，这一操作的初衷是对可能接连而来的针对于该节点的访问进行快捷响应。好比你正在刷视频，你突然看了一个平常不常看的类型的视频，对于大数据来说，你的某次访问就预示着你接下来也可能会“沉迷”于此类视频，因而把这类视频的优先级提高，并作出快速响应。在存储了巨量数据的数据库里，把某类键值的优先级提高是常见加快查询速度的方式之一。

对于三个节点 ，我们在操作时一般会遇见如下的几种排布方式：

1. 线形，即三个点都伸向相同方向
2. 折线形，伸展方向不相同

对于第一种情况， 给出的策略是先转 后转 ；第二种情况则转两次 。这样的旋转方式经过证明可以让整个算法的时间复杂度均摊在 左右。

我们定义 为：将节点 旋转成 的一个子节点，特殊地，如果 ，就代表将 转到根节点下。那么当 的子节点不是 时，就不断旋转直到符合要求，期间判断三点形态（线形、折线形），然后采取对应的旋转策略即可。

1
void splay(int x, int k) {
2
    while (tree[x].p != k) {
3
        int y = tree[x].p, z = tree[y].p;           // Father and grandfather
4
        int sn_pos = (tree[y].s[1] == x);           // Son direction
5
        int fa_pos = (tree[z].s[1] == y);           // Father direction
6
        if (z != k) {
7
            // More than one rotation to go
8
            if (sn_pos == fa_pos) rotate(y);        // Linear
9
            else rotate(x);                         // Broken-linear
10
        }
11
        rotate(x);                                  // Anyhow X needs a rotation
12
    }
13
    if (!k) root = x;                               // Upgrade as the new root
14
}

前驱&后继Precursor & Successor#

为了找前驱/后继，我们就先需要找到带有给定权值的点。将这个点提到根上，方便我们的求解。基本思路和 一样，都是一头走到黑地向子树里面找。

1
void findAndRaise(int idx, int dat) {
2
    splay(idx);
3
    if (tree[idx].dat > dat) findAndRaise(tree[idx].s[0], dat);
4
    else if (tree[idx].dat < dat) findAndRaise(tree[idx].s[1], dat);
5
}
6

7
int precursor(int dat) {
8
    findAndRaise(root, dat);
9
    int tmp = root;
10
    if (tree[tmp].s[0]) {
11
        tmp = tree[tmp].s[0];
12
        while (tree[tmp].s[1]) tmp = tree[tmp].s[1];
13
        return tmp;
14
    }
15
    return tmp;
16
}
17

18
int successor(int dat) {
19
    findAndRaise(root, dat);
20
    int tmp = root;
21
    if (tree[tmp].s[1]) {
22
        tmp = tree[tmp].s[1];
23
        while (tree[tmp].s[0]) tmp = tree[tmp].s[0];
24
        return tmp;
25
    }
26
    return tmp;
27
}

插入操作Insertion#

1
int allocate(int dat, int p) {
2
    idx++;
3
    tree[idx].dat = dat;
4
    tree[idx].p = p;
5
    tree[idx].cnt = 1;
6
    tree[idx].size = 1;
7
    return idx;
8
}
9

10
void insert(int dat) {
11
    int u = root, p = 0;
12
    while (u) {
13
        p = u;
14
        if (tree[p].dat > dat) u = tree[u].s[0];
15
        else if (tree[p].dat < dat) u = tree[u].s[1];
16
        else {
17
            tree[u].cnt++;
18
            splay(p);
19
            return;
20
        }
21
    }
22
    u = allocate(dat, p);
23
    if (p) {
24
        // Not first run
25
        if (tree[p].dat > dat) tree[p].s[0] = u;
26
        else tree[p].s[1] = u;
27
    }
28
    splay(u);
29
}

1
void insertInterval(int pos, int tot) {
2
    int l = getIdxByRank(root, pos + 1);
3
    int r = getIdxByRank(root, pos + 2);
4
    splay(l);
5
    splay(r, l);
6
    int rt = build(0, tot - 1, r);
7
    tree[r].s[0] = rt;
8
    update(r);
9
    update(l);
10
}

删除操作Deletion#

1
void removeNode(int idx, int dat) {
2
    int pre = precursor(dat);
3
    int suc = successor(dat);
4
    splay(pre);
5
    splay(suc, pre);
6
    int tar = tree[suc].s[0];
7
    if (tree[tar].cnt > 1) {
8
        tree[tar].cnt--;
9
        splay(tar);
10
    } else tree[suc].s[0] = 0;
11
}

1
void removeInterval(int pos, int tot) {
2
    int l = getIdxByRank(root, pos);
3
    int r = getIdxByRank(root, pos + tot + 1);
4
    splay(l);
5
    splay(r, l);
6
    gc(tree[r].s[0]);
7
    tree[r].s[0] = 0;
8
    update(r);
9
    update(l);
10
}

1
int getRankByData(int idx, int dat) {
2
    if (!idx) return 1;
3
    if (tree[idx].dat > dat) return getRankByData(tree[idx].s[0], dat) + 1;
4
    return getRankByData(tree[idx].s[1], dat) + (tree[idx].s[0] ? leftSubtree(idx).size : 0) + tree[idx].cnt;
5
}
6

7
int getDataByRank(int idx, int rank) {
8
    if (!idx) return -INF;
9
    if (leftSubtree(idx).size >= rank) return getDataByRank(tree[idx].s[0], rank);
10
    if (leftSubtree(idx).size + tree[idx].cnt >= rank) return tree[idx].dat;
11
    return getDataByRank(tree[idx].s[1], rank - (tree[idx].s[0] ? leftSubtree(idx).size : 0) - tree[idx].cnt);
12
}

区间翻转Sequence Flipping#

在开始之前，我们首先要明白区间翻转在 里的呈现是怎样的。显然，翻转前后，伸展树的中序遍历是相反的，那就可以画出如下对比图：

可以发现，这个序列翻转了，在图中的表现就是交换树的左右儿子。我们类比线段树，可以引入一个懒标记来记录区间翻转操作。当然这里的标记打法和线段树略有不同：

给 打标记的时候 这个点的左右儿子还没换，这与线段树的 lazytag 不同。线段树在 上打标记，表示 已经修改过了，将要修改儿子的贡献。

——樱雪喵 《Splay 详细图解 & 轻量级代码实现》

那如何找到区间 所在子树呢？其实你已经学过了，就在前边的区间删除中，分别找到左右端点的前驱和后继，然后旋转到一起，后继的左子树就是 。为了防止找不到前驱和后继，我们在整个序列的一头一尾分别插入两个点，以防访问出错，我们的边界节点恰好就能做到这一点！

如果要进行如上的翻转操作，整个代码中就要加入下传标记的操作。在所有有关查找的地方加入标记下传即可。

1
void pushdown(int idx) {
2
    if (tree[idx].tag) {
3
        swap(tree[idx].s[0], tree[idx].s[1]);
4
        leftSubtree(idx).tag ^= 1;
5
        rightSubtree(idx).tag ^= 1;
6
        tree[idx].tag = 0;
7
    }
8
}

在查询排名和数值的时候下传标记即可。

启发式合并Heuristic Merging#

的合并就是单纯的将其中一棵树的每个点插入另一棵树中，但是这样可能会出现效率问题。当你把一个拥有很多节点的树合并到一棵非常小的树中时，由于插入操作的次数取决于插入子树的大小，显然会导致效率浪费。出于节省效率的目的，我们把大小更小的树合并到大小更大的树上去。

在这期间，我们就需要一个并查集来维护每个点所在的子树，把维护根节点的整型换成一个数组（毕竟有很多子树需要维护根节点的值）。在伸展操作（旋转到根节点）时更新根信息即可。

洛谷 P3391 [模板] 文艺平衡树#

题目地址：P3391

题目难度：提高+/省选-

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 ，翻转区间是 的话，结果是 。

输入格式：

第一行两个正整数 ，表示序列长度与操作个数。序列中第 项初始为 。 接下来 行，每行两个正整数 ，表示翻转的区间。

输出格式：

输出一行 个正整数，表示原始序列经过 次变换后的结果。

数据范围：

对于 的数据，，。

这道题额外涉及到一个知识点，输出树的中序遍历。我们知道中序遍历是按照“左-根-右”的顺序递归输出的，我们只需要判断是否存在左右子树，然后递归输出即可，注意特判首位的边界节点。

代码在云剪切板。

洛谷 P3224 [HNOI2012] 永无乡#

题目地址：P3224

题目难度：省选/NOI-

题目来源：湖南  2012  各省省选

永无乡包含 座岛，编号从 到 ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 座岛排名，名次用 到 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 出发经过若干座（含 座）桥可以 到达岛 ，则称岛 和岛 是连通的。

现在有两种操作：

B x y 表示在岛 与岛 之间修建一座新桥。

Q x k 表示询问当前与岛 连通的所有岛中第 重要的是哪座岛，即所有与岛 连通的岛中重要度排名第 小的岛是哪座，请你输出那个岛的编号。

输入格式：

第一行是用空格隔开的两个整数，分别表示岛的个数 以及一开始存在的桥数 。

第二行有 个整数，第 个整数表示编号为 的岛屿的排名 。

接下来 行，每行两个整数 ，表示一开始存在一座连接编号为 的岛屿和编号为 的岛屿的桥。

接下来一行有一个整数，表示操作个数 。

接下来 行，每行描述一个操作。每行首先有一个字符 ，表示操作类型，然后有两个整数 。

• 若 为 Q，则表示询问所有与岛 连通的岛中重要度排名第 小的岛是哪座，请你输出那个岛的编号。
• 若 为 B，则表示在岛 与岛 之间修建一座新桥。

输出格式：

对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 。

数据范围：

• 对于 的数据，保证 , 。
• 对于 的数据，保证 , ， 为一个 的排列，，。

这道题就要运用到我们上边所讲的启发式合并。重定义我们的 为把节点 旋转到编号 的树的 号点下（默认 即旋转到根）；以及插入函数 为把权值和原编号（合并操作会增加新点，为了保证下标稳定故初始化时记录）分别为 的点插入到 号树下。那么每一次合并，我们只需要判断合并的两点是否已经在同一棵树下、两棵树哪一棵的大小更大（启发式），然后用一个深搜遍历小树，把小树里的点递归插入（复制）到大树里面即可。注意操作时用 root 数组包裹的地方，理解为重。

代码在云剪切板中。

洛谷 P2042 [NOI2005] 维护数列#

题目地址：P2042

题目难度：省选/NOI

题目来源：NOI  2005

请写一个程序，要求维护一个数列，支持以下 种操作：

| 编号 | 名称 | 格式 | 说明 | | :—: | :----------: | :------------------------------------------------------------: | :---------------------------------------------------------------------------------------------------------- | | 1 | 插入 | | 在当前数列的第 个数字后插入 个数字：；若在数列首插入，则 为 | | 2 | 删除 | | 从当前数列的第 个数字开始连续删除 个数字 | | 3 | 修改 | | 从当前数列的第 个数字开始的连续 个数字统一修改为 | | 4 | 翻转 | | 取出从当前数列的第 个数字开始的 个数字，翻转后放入原来的位置 | | 5 | 求和 | | 计算从当前数列的第 个数字开始的 个数字的和并输出 | | 6 | 求最大子列和 | | 求出当前数列中和最大的一段子列，并输出最大和 |

输入格式：

第一行包含两个整数 和 ， 表示初始时数列中数的个数， 表示要进行的操作数目。

第二行包含 个数字，描述初始时的数列。以下 行，每行一条命令，格式参见问题描述中的表格。

输出格式：

对于输入数据中的 和 操作，向输出文件依次打印结果，每个答案（数字）占一行。

数据范围：

• 你可以认为在任何时刻，数列中至少有 个数。
• 输入数据一定是正确的，即指定位置的数在数列中一定存在。
• 对于 的数据，任何时刻数列中最多含有 个数。
• 对于 的数据，任何时刻数列中最多含有 个数，任何时刻数列中任何一个数字均在 内，，插入的数字总数不超过 。

题面由 @syksykCCC 提供。

这道题需要我们复习一下之前线段树的知识，这篇博客介绍了线段树求解区间最大子列的方法。

代码在云剪贴板。