Splay树与懒惰标记：高效解决蓝桥杯“冰山”动态集合维护难题

1. 项目概述：当“冰山”遇上Splay树

如果你参加过蓝桥杯国赛，或者刷过它的真题，那你一定对那种“题目描述看似简单，但数据规模巨大，常规数据结构直接超时”的压迫感记忆犹新。第十二届国赛的“冰山”这道题，就是这种风格的典型代表。乍一看，题目描述可能像是一个关于数组元素增减的模拟题，但当你看到数据范围——操作次数高达10^5，元素值变化范围巨大——你就会明白，朴素的数组遍历或者简单的平衡二叉树（如std::set）都可能力不从心。这时，一个更强大、更灵活的数据结构就必须登场了，它就是Splay树。

这道题的核心，是要求我们高效维护一个动态集合，支持三种操作：1. 给所有元素加上一个值；2. 给所有元素减去一个值，并将低于某个阈值的元素删除；3. 查询当前集合中第K小的元素。全局加减操作意味着每个元素的值都在实时、同量地变化，这直接否决了直接存储元素原始值的方案。而频繁的删除和查询，要求我们的数据结构必须能高效地支持动态增删和基于排名的查询。Splay树，凭借其“伸展”操作能将任意节点旋转到根部的特性，天然适合处理这种需要频繁访问和修改局部结构的场景。它不仅仅是平衡，更是“自适应”的平衡，能将热点数据快速调整到根部，从而加速后续操作。

所以，这篇题解的目的，不是简单地贴出一段AC代码，而是带你彻底拆解“冰山”一题，理解为什么Splay树是近乎“量身定做”的解决方案，并一步步构建起我们自己的Splay树，最终攻克这道难题。无论你是正在备赛的选手，还是对高级数据结构感兴趣的学习者，这篇文章都将从原理到实现细节，给你一份清晰的“作战地图”。

2. 核心思路与数据结构选型分析

面对“冰山”问题，我们首先需要摒弃模拟每个冰山个体变化的思维。10^5次操作，如果每次加减都遍历所有N个元素（N也可以很大），时间复杂度将是灾难性的O(N * M)。我们必须找到一个能批量处理全局变化，同时又能快速定位和修改个体的表示方法。

2.1 问题重述与建模

让我们把问题抽象一下：

• 我们维护一个可重集合 S（初始有N个冰山，大小可能相同）。
• 操作1（k）： 令集合中每个元素的值增加k。
• 操作2（k）： 令集合中每个元素的值减少k。随后，将所有值小于1的元素从集合中删除。
• 操作3（k）： 查询当前集合中第k小的元素的值。注意，k是基于当前集合大小的排名。

关键难点：操作1和操作2是作用于全体元素的。如果我们存储元素的绝对值，每次全局加减都需要遍历整棵树进行修改，单次操作O(N)无法接受。

2.2 懒惰标记（Delta）的引入

这是本题的第一个核心技巧。我们不在树节点中直接存储冰山的“绝对大小”，而是存储它的“相对大小”。我们引入一个全局偏移量delta。

• 初始时，delta = 0。我们读入初始冰山大小val，然后将val直接插入Splay树中。此时，冰山的真实大小= 节点存储值val+delta。
• 执行操作1（加k）：我们不需要修改树中的任何节点！只需要让delta += k。此时，所有节点的真实大小 = 节点值 + 新的delta，相当于全体增加了k。
• 执行操作2（减k）：同样，我们让delta -= k。但是，减操作后需要删除所有真实大小< 1的冰山。由于真实大小 = 节点值 + delta，所以条件等价于节点值 < 1 - delta。

这个技巧将全局修改的成本从O(N)降到了O(1)，代价是我们在进行所有涉及节点值比较的操作（如插入、删除、查询）时，都需要考虑delta的影响，使用“真实大小”进行逻辑判断。

2.3 为什么是Splay树？

有了delta处理全局加减，我们还需要一个数据结构来处理动态的插入、删除和查询第k小。候选者通常有：

1. 数组+排序： 删除和插入需要移动元素，O(N)，不可行。
2. 二叉搜索树（BST）： 如果不平衡，在极端数据下会退化成链表，O(N)。
3. 红黑树（如std::multiset）： 平衡性好，支持插入、删除、查找第k小（通过迭代器移动，O(k)），但对于本题频繁的按值域删除（删除所有小于x的节点）和查询第k小，std::multiset的接口并不直接高效。按值域删除需要找到边界然后循环删除，并非最优。
4. 权值线段树/树状数组： 如果值域范围可以离散化且不大，这是非常好的选择，查询第k小是O(log V)。但本题冰山大小变化范围没有明确上限，delta的累积可能使值域非常大，离散化困难且动态扩展麻烦。
5. Splay树： 它完美契合了本题的需求：
   • 高效的按值域分裂： Splay树的核心操作splay可以将任意节点旋转到根。我们可以利用这一点，实现一个split函数：将树中所有值小于key的节点分裂到左子树，大于等于key的节点留在右子树。这个操作是O(log N)的。对于操作2，我们只需要找到split_key = 1 - delta，然后将左子树（所有需要删除的节点）整棵丢弃即可。
   • 高效查询第k小： Splay树的节点可以维护子树大小size。查询第k小时，我们可以从根开始，根据左子树的size决定搜索左子树、输出当前根还是搜索右子树，复杂度O(log N)。
   • 自适应优化： 频繁操作的值（如边界值）会被splay到根部，后续访问更快。

因此，Splay树 + 全局懒惰标记delta，构成了解决“冰山”问题的最优组合。前者负责高效的动态集合维护，后者负责O(1)时间处理全局修改。

2.4 数据结构设计

我们的Splay树节点需要存储以下信息：

struct Node { int ch[2]; // 左右孩子索引，0表示空 int fa; // 父亲索引 long long val; // 节点存储的“相对值” int cnt; // 当前相同值的数量（处理可重集合） int size; // 子树大小（包括cnt） // 构造函数 Node(long long v = 0) : val(v), cnt(1), size(1) { ch[0] = ch[1] = fa = 0; } };

重要：val存储的是相对值。节点的真实值=val + delta（delta是一个全局变量）。

我们还需要一些全局变量和函数框架：

• int root, tot： 根节点索引和节点总数。
• long long delta： 全局偏移量。
• Node tr[MAXN]： 节点池。
• 核心Splay操作：rotate,splay,insert,find（按值查找节点并将其splay到根），get_kth（查询第k小），split（按值分裂），merge（合并两棵树）。

3. Splay树核心操作实现与“冰山”适配

在这一部分，我们将深入Splay树的实现细节，并重点讲解如何为了“冰山”这道题修改和适配标准模板。

3.1 基础维护操作：pushup与旋转

任何平衡树的基础都是维护节点信息和保持平衡。

pushup函数： 在节点信息发生变化（如旋转、插入后）更新当前节点的size。

void pushup(int x) { if (x) { tr[x].size = tr[x].cnt; if (tr[x].ch[0]) tr[x].size += tr[tr[x].ch[0]].size; if (tr[x].ch[1]) tr[x].size += tr[tr[x].ch[1]].size; } }

注意： 一定要先判断子节点是否存在（索引不为0）再访问其size，否则会访问到未初始化的节点导致错误。

rotate函数： Splay树的单旋操作，和AVL树类似，目的是将节点x上移一层，同时保持BST性质。

// 判断x是其父节点的左孩子(0)还是右孩子(1) int get(int x) { return tr[tr[x].fa].ch[1] == x; } void rotate(int x) { int y = tr[x].fa, z = tr[y].fa; int k = get(x); // x在y的哪一侧 // 第一步：处理x和y的另一个孩子的关系 tr[y].ch[k] = tr[x].ch[k ^ 1]; if (tr[x].ch[k ^ 1]) tr[tr[x].ch[k ^ 1]].fa = y; // 第二步：处理x和y的父子关系 tr[x].ch[k ^ 1] = y; tr[y].fa = x; // 第三步：处理x和z的父子关系 tr[x].fa = z; if (z) tr[z].ch[tr[z].ch[1] == y] = x; // 更新信息，先更新子节点y，再更新父节点x pushup(y); pushup(x); }

旋转是splay的基石，理解这三步交换指针的过程至关重要。可以画图辅助理解。

3.2 灵魂操作：splay

splay(x, goal)函数是Splay树的灵魂，它将节点x通过一系列旋转移动到goal节点的子节点位置（通常goal=0表示移动到根）。

void splay(int x, int goal) { // 如果goal为0，则将x旋转为根 while (tr[x].fa != goal) { int y = tr[x].fa; int z = tr[y].fa; if (z != goal) { // 折线型（之字形）需要先旋转父节点 if (get(x) != get(y)) { rotate(x); // 之字形，旋转x } else { rotate(y); // 一字型，先旋转y } } rotate(x); // 最后再旋转一次x } if (goal == 0) root = x; // 如果目标是根，更新根节点 }

splay操作不仅将x移到了目标位置，更重要的是，它让访问路径上的节点变得“更平衡”，这是一种摊还O(log N)的操作。

在“冰山”中的应用： 我们几乎在每个核心操作后都会进行splay，以维护树的平衡性和加速后续操作。例如，在insert一个值后，我们会将新插入的节点splay到根。

3.3 关键操作实现：插入、查找、分裂与合并

这些操作是解决本题的“工具”。

1. 插入（insert）我们需要插入的是冰山的“相对值”。由于存在全局delta，调用插入时传入的参数v应该是真实值 - delta。

void insert(long long v) { if (!root) { // 树为空，创建根节点 root = ++tot; tr[tot] = Node(v); return; } int cur = root, p = 0; while (cur && tr[cur].val != v) { p = cur; cur = tr[cur].ch[v > tr[cur].val]; // 根据大小决定方向 } if (cur) { // 值已存在，增加计数 tr[cur].cnt++; } else { // 创建新节点 cur = ++tot; tr[cur] = Node(v); tr[cur].fa = p; if (p) tr[p].ch[v > tr[p].val] = cur; } pushup(cur); pushup(p); splay(cur, 0); // 将新节点伸展到根，保持平衡 }

2. 查找（find）查找一个值v（相对值）所在的节点，并将其splay到根。如果找不到，则把查找路径上最后一个节点splay到根，这有利于后续操作（如插入前驱后继）。

void find(long long v) { if (!root) return; int cur = root; while (tr[cur].ch[v > tr[cur].val] && v != tr[cur].val) { cur = tr[cur].ch[v > tr[cur].val]; } splay(cur, 0); // 将找到的节点（或最后一个访问的节点）伸展到根 }

3. 分裂（split）这是本题最核心的操作之一。目标：将树中所有值小于key的节点分裂到左子树，其余节点留在右子树。函数返回左子树的根节点索引。 实现思路：

• 插入一个值为key的虚拟节点（或者找到key的前驱/后继）。
• 将其splay到根。
• 此时，根的左子树的所有值都小于key，右子树的所有值都大于等于key。
• 我们切断根与左子树的连接，并返回左子树的根。

更稳健的实现是使用find和找前驱的方法：

// 分裂出所有值 < key 的节点，返回左子树根 int split(long long key) { find(key); // 尝试找到key，找不到也会把最后一个节点splay到根 if (tr[root].val < key) { // 根节点的值小于key，那么整个左子树+根都小于key int left_root = root; root = tr[root].ch[1]; if (root) tr[root].fa = 0; tr[left_root].ch[1] = 0; pushup(left_root); return left_root; } else { // 根节点的值 >= key，那么小于key的节点只可能在左子树 int left_root = tr[root].ch[0]; if (left_root) { tr[left_root].fa = 0; tr[root].ch[0] = 0; pushup(root); } return left_root; } }

实操心得： 分裂操作边界情况很多（树空、key比所有值都小/大）。上述写法通过find统一处理，逻辑相对清晰。关键在于理解执行find(key)并splay后，根节点所处的位置与key的关系，是决定如何切分的关键。

4. 合并（merge）将两棵Splay树left和right合并，前提是left树中的所有值都小于right树中的所有值。

void merge(int left, int right) { if (!left) { root = right; return; } if (!right) { root = left; return; } // 找到left树中的最大值节点，将其splay到left的根 int cur = left; while (tr[cur].ch[1]) cur = tr[cur].ch[1]; splay(cur, 0); // 此时cur是left的根，且没有右孩子 // 将right树作为cur的右子树 tr[cur].ch[1] = right; tr[right].fa = cur; pushup(cur); root = cur; }

在“冰山”题中，合并操作使用场景较少，但它是Splay树的标准操作。

3.4 查询第k小（get_kth）

由于我们维护了子树大小size，查询排名为k的元素（1-indexed）就非常高效。

long long get_kth(int k) { int cur = root; if (tr[cur].size < k) return -1; // 不存在第k小 while (true) { int left_size = tr[cur].ch[0] ? tr[tr[cur].ch[0]].size : 0; if (k <= left_size) { cur = tr[cur].ch[0]; } else if (k <= left_size + tr[cur].cnt) { break; // 找到目标节点 } else { k -= left_size + tr[cur].cnt; cur = tr[cur].ch[1]; } } splay(cur, 0); // 将查询到的节点splay到根，优化后续访问 return tr[cur].val + delta; // 返回真实值！！！ }

极其重要的细节： 返回的是tr[cur].val + delta，因为节点存储的是相对值，查询结果需要还原为真实值。这是本题最容易出错的地方之一。

4. “冰山”问题完整解题流程与代码实现

现在，我们将所有模块组合起来，形成完整的解题逻辑。假设我们已正确实现了上述Splay树的所有函数。

4.1 主逻辑框架

#include <iostream> using namespace std; const int MAXN = 1000010; // 根据操作次数和插入数量估算 struct Node { /* 如前文定义 */ }; Node tr[MAXN]; int root, tot; long long delta = 0; // 全局偏移量 // 此处插入之前实现的所有Splay树函数：pushup, get, rotate, splay, insert, find, split, get_kth, merge int main() { int n, m; scanf("%d %d", &n, &m); // 初始化：插入初始冰山 for (int i = 0; i < n; ++i) { long long x; scanf("%lld", &x); insert(x - delta); // 插入相对值 } while (m--) { int t; long long k; scanf("%d %lld", &t, &k); if (t == 1) { // 全局加k delta += k; } else if (t == 2) { // 全局减k，并删除真实值小于1的冰山 delta -= k; long long split_key = 1 - delta; // 计算分裂的边界相对值 int left_tree = split(split_key); // 分裂出所有值 < split_key 的节点 // left_tree 整棵树就是需要删除的冰山，直接丢弃即可 // root 现在是剩余的部分（值 >= split_key） // 注意：如果分裂后树为空，需要处理root=0的情况 if (root == 0) { // 如果所有冰山都被删除，树为空 // 根据题目，可能需要进行特殊处理，但通常继续即可 } } else if (t == 3) { // 查询第k小 if (root == 0 || tr[root].size < k) { printf("-1\n"); // 集合中元素不足k个 } else { long long real_val = get_kth(k); // get_kth内部已加delta printf("%lld\n", real_val); } } } return 0; }

4.2 操作2的深度解析与边界处理

操作2是本题最易错、最需要小心处理的部分。让我们再仔细捋一遍：

1. delta -= k。
2. 计算分裂键值split_key = 1 - delta。这个值的意义是：任何存储值（相对值）小于split_key的节点，其真实值val + delta都小于 1。
3. 调用split(split_key)。这个函数会修改全局root，使其指向分裂后值>= split_key的子树。同时，它返回被分裂出来的、值< split_key的左子树的根。
4. 我们直接丢弃返回的左子树根节点。在内存池的实现中，丢弃意味着我们不再关心这些节点，它们占用的索引不会被回收（简易实现中）。在更严谨的实现中，可以考虑内存回收，但竞赛中通常不需要。
5. 分裂后，root可能为空（如果所有节点都被删除）。后续操作需要判断root是否为空。

一个致命的边界情况： 当split_key大于树中所有值时，split函数的行为是什么？在我们的实现中，find(split_key)会将最大值节点splay到根，且该节点值< split_key。根据split函数逻辑，会返回整个树的根，并将root置为0。这是正确的，意味着所有冰山都被删除。

另一个边界： 当split_key小于树中所有值时，split会返回0（左子树为空），root保持不变。这意味着没有冰山被删除。

确保你的split函数能正确处理这些情况。

4.3 代码实现中的优化与技巧

1. 内存池与节点索引： 使用数组tr和索引tot来管理节点，比动态分配new Node()快得多，也避免内存泄漏。
2. long long类型： 冰山大小、delta、操作值k都可能很大，必须使用long long防止溢出。
3. 输入输出优化： 使用scanf/printf而非cin/cout，在大量数据读入时能显著提升性能。
4. 空树判断： 在执行get_kth或splay操作前，养成判断root是否为0的习惯。
5. splay的摊还复杂度： 虽然单次splay可能不是O(log N)，但连续M次操作的总时间复杂度是O(M log N)，可以放心使用。

5. 常见问题、调试技巧与思维延伸

即使理解了算法，实现Splay树也常伴随着各种Bug。这里分享一些常见的坑和调试方法。

5.1 常见问题速查表

5.2 调试技巧

1. 编写打印函数： 实现一个中序遍历打印树的函数，以及一个打印节点详细信息的函数（包括索引、值、左右孩子、父亲、size、cnt）。这是调试平衡树最有力的工具。

   void dfs_print(int u) { if (!u) return; dfs_print(tr[u].ch[0]); cout << "Node " << u << ": val=" << tr[u].val << ", cnt=" << tr[u].cnt << ", size=" << tr[u].size << ", fa=" << tr[u].fa << ", lch=" << tr[u].ch[0] << ", rch=" << tr[u].ch[1] << endl; dfs_print(tr[u].ch[1]); }

2. 小数据对拍： 写一个暴力程序（用vector模拟所有操作），生成随机小数据（N和M在20以内），对比两个程序的最终结果和每次查询的结果。这是定位逻辑错误最有效的方法。
3. 单元测试： 不要一下子写完整程序。先单独测试insert和get_kth（不带delta），再测试split功能，最后整合delta和主逻辑。
4. 关注指针与索引： Splay树满是指针操作。确保在任何修改ch或fa的地方，都同步更新对应节点的反向指针。例如，tr[x].ch[1] = y之后，通常需要tr[y].fa = x。

5.3 思维延伸与优化

1. 删除节点的内存回收： 上述实现中，被split丢弃的节点索引没有被复用。在操作次数极多时，可能导致tot超过MAXN。可以维护一个栈来回收删除的节点索引，在insert时优先从栈中取索引。
2. 非旋转Treap (FHQ Treap) 作为替代： 本题同样可以使用FHQ Treap解决，其核心操作split和merge更为直观，代码实现可能比Splay树更简短，且同样高效。对于觉得Splay树旋转复杂的同学，FHQ Treap是另一个绝佳选择。其split操作直接按值将树分成两棵，完美契合本题需求。
3. 理解“摊还”复杂度： Splay树的单次操作复杂度可能不是严格的O(log N)，但一系列操作的总时间是O(M log N)。这种“摊还”分析思想在算法竞赛中很重要，像并查集路径压缩、向量动态数组(vector)的扩容都是摊还复杂度的例子。

攻克“冰山”这道题，其意义远不止于通过一次比赛。它强迫你深入理解一种强大的、灵活的数据结构，并掌握“懒惰标记”这种将全局修改转化为局部判断的经典思想。当你再遇到需要维护动态序列、支持区间操作和快速查询的问题时，你会想起来，你工具箱里还有Splay树这把瑞士军刀。实现过程中调试的煎熬，最终都会转化为对指针、递归、树形结构更深的理解。