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个冰山大小可能相同。操作1k 令集合中每个元素的值增加k。操作2k 令集合中每个元素的值减少k。随后将所有值小于1的元素从集合中删除。操作3k 查询当前集合中第k小的元素的值。注意k是基于当前集合大小的排名。关键难点操作1和操作2是作用于全体元素的。如果我们存储元素的绝对值每次全局加减都需要遍历整棵树进行修改单次操作O(N)无法接受。2.2 懒惰标记Delta的引入这是本题的第一个核心技巧。我们不在树节点中直接存储冰山的“绝对大小”而是存储它的“相对大小”。我们引入一个全局偏移量delta。初始时delta 0。我们读入初始冰山大小val然后将val直接插入Splay树中。此时冰山的真实大小 节点存储值valdelta。执行操作1加k我们不需要修改树中的任何节点只需要让delta k。此时所有节点的真实大小 节点值 新的delta相当于全体增加了k。执行操作2减k同样我们让delta - k。但是减操作后需要删除所有真实大小 1的冰山。由于真实大小 节点值 delta所以条件等价于节点值 1 - delta。这个技巧将全局修改的成本从O(N)降到了O(1)代价是我们在进行所有涉及节点值比较的操作如插入、删除、查询时都需要考虑delta的影响使用“真实大小”进行逻辑判断。2.3 为什么是Splay树有了delta处理全局加减我们还需要一个数据结构来处理动态的插入、删除和查询第k小。候选者通常有数组排序 删除和插入需要移动元素O(N)不可行。二叉搜索树BST 如果不平衡在极端数据下会退化成链表O(N)。红黑树如std::multiset 平衡性好支持插入、删除、查找第k小通过迭代器移动O(k)但对于本题频繁的按值域删除删除所有小于x的节点和查询第k小std::multiset的接口并不直接高效。按值域删除需要找到边界然后循环删除并非最优。权值线段树/树状数组 如果值域范围可以离散化且不大这是非常好的选择查询第k小是O(log V)。但本题冰山大小变化范围没有明确上限delta的累积可能使值域非常大离散化困难且动态扩展麻烦。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 deltadelta是一个全局变量。我们还需要一些全局变量和函数框架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 灵魂操作splaysplay(x, goal)函数是Splay树的灵魂它将节点x通过一系列旋转移动到goal节点的子节点位置通常goal0表示移动到根。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 // 注意如果分裂后树为空需要处理root0的情况 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是本题最易错、最需要小心处理的部分。让我们再仔细捋一遍delta - k。计算分裂键值split_key 1 - delta。这个值的意义是任何存储值相对值小于split_key的节点其真实值val delta都小于 1。调用split(split_key)。这个函数会修改全局root使其指向分裂后值 split_key的子树。同时它返回被分裂出来的、值 split_key的左子树的根。我们直接丢弃返回的左子树根节点。在内存池的实现中丢弃意味着我们不再关心这些节点它们占用的索引不会被回收简易实现中。在更严谨的实现中可以考虑内存回收但竞赛中通常不需要。分裂后root可能为空如果所有节点都被删除。后续操作需要判断root是否为空。一个致命的边界情况 当split_key大于树中所有值时split函数的行为是什么在我们的实现中find(split_key)会将最大值节点splay到根且该节点值 split_key。根据split函数逻辑会返回整个树的根并将root置为0。这是正确的意味着所有冰山都被删除。另一个边界 当split_key小于树中所有值时split会返回0左子树为空root保持不变。这意味着没有冰山被删除。确保你的split函数能正确处理这些情况。4.3 代码实现中的优化与技巧内存池与节点索引 使用数组tr和索引tot来管理节点比动态分配new Node()快得多也避免内存泄漏。long long类型 冰山大小、delta、操作值k都可能很大必须使用long long防止溢出。输入输出优化 使用scanf/printf而非cin/cout在大量数据读入时能显著提升性能。空树判断 在执行get_kth或splay操作前养成判断root是否为0的习惯。splay的摊还复杂度 虽然单次splay可能不是O(log N)但连续M次操作的总时间复杂度是O(M log N)可以放心使用。5. 常见问题、调试技巧与思维延伸即使理解了算法实现Splay树也常伴随着各种Bug。这里分享一些常见的坑和调试方法。5.1 常见问题速查表问题现象可能原因检查点与解决方案输出错误或随机值1. 没有使用long long导致溢出。2. 查询第k小时忘记加delta。3. 节点信息size维护错误。1. 检查所有与值相关的变量是否为long long。2. 在get_kth函数中确认返回的是val delta。3. 在rotate和insert后检查是否调用了pushup且顺序正确先更新子节点再更新父节点。程序运行超时1.splay操作写错导致死循环或退化。2. 分裂/合并操作逻辑错误使树不平衡。3. 输入输出未优化。1. 检查get(x)函数是否正确判断了左右孩子。2. 检查splay中的双旋条件 (get(x) get(y))。3. 对拍小数据观察树的高度是否增长异常。分裂操作后树状态异常1.split函数中指针切断和父节点更新有遗漏。2. 对find后根节点值与key的关系判断逻辑有误。1. 画图模拟分裂过程仔细检查每一步的fa和ch指针修改。2. 用一组简单数据如{1,3,5}测试分裂key2, key0, key6的情况打印树的结构。查询第k小结果不对1.size维护错误。2.get_kth中k的缩减逻辑错误。3. 存在重复元素(cnt1)时判断条件k left_size tr[cur].cnt写错。1. 在每次可能改变树结构的操作后打印根节点的size看是否符合预期。2. 单步调试get_kth观察k、left_size、cnt的变化。5.2 调试技巧编写打印函数 实现一个中序遍历打印树的函数以及一个打印节点详细信息的函数包括索引、值、左右孩子、父亲、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]); }小数据对拍 写一个暴力程序用vector模拟所有操作生成随机小数据N和M在20以内对比两个程序的最终结果和每次查询的结果。这是定位逻辑错误最有效的方法。单元测试 不要一下子写完整程序。先单独测试insert和get_kth不带delta再测试split功能最后整合delta和主逻辑。关注指针与索引 Splay树满是指针操作。确保在任何修改ch或fa的地方都同步更新对应节点的反向指针。例如tr[x].ch[1] y之后通常需要tr[y].fa x。5.3 思维延伸与优化删除节点的内存回收 上述实现中被split丢弃的节点索引没有被复用。在操作次数极多时可能导致tot超过MAXN。可以维护一个栈来回收删除的节点索引在insert时优先从栈中取索引。非旋转Treap (FHQ Treap) 作为替代 本题同样可以使用FHQ Treap解决其核心操作split和merge更为直观代码实现可能比Splay树更简短且同样高效。对于觉得Splay树旋转复杂的同学FHQ Treap是另一个绝佳选择。其split操作直接按值将树分成两棵完美契合本题需求。理解“摊还”复杂度 Splay树的单次操作复杂度可能不是严格的O(log N)但一系列操作的总时间是O(M log N)。这种“摊还”分析思想在算法竞赛中很重要像并查集路径压缩、向量动态数组(vector)的扩容都是摊还复杂度的例子。攻克“冰山”这道题其意义远不止于通过一次比赛。它强迫你深入理解一种强大的、灵活的数据结构并掌握“懒惰标记”这种将全局修改转化为局部判断的经典思想。当你再遇到需要维护动态序列、支持区间操作和快速查询的问题时你会想起来你工具箱里还有Splay树这把瑞士军刀。实现过程中调试的煎熬最终都会转化为对指针、递归、树形结构更深的理解。 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个冰山大小可能相同。操作1k 令集合中每个元素的值增加k。操作2k 令集合中每个元素的值减少k。随后将所有值小于1的元素从集合中删除。操作3k 查询当前集合中第k小的元素的值。注意k是基于当前集合大小的排名。关键难点操作1和操作2是作用于全体元素的。如果我们存储元素的绝对值每次全局加减都需要遍历整棵树进行修改单次操作O(N)无法接受。2.2 懒惰标记Delta的引入这是本题的第一个核心技巧。我们不在树节点中直接存储冰山的“绝对大小”而是存储它的“相对大小”。我们引入一个全局偏移量delta。初始时delta 0。我们读入初始冰山大小val然后将val直接插入Splay树中。此时冰山的真实大小 节点存储值valdelta。执行操作1加k我们不需要修改树中的任何节点只需要让delta k。此时所有节点的真实大小 节点值 新的delta相当于全体增加了k。执行操作2减k同样我们让delta - k。但是减操作后需要删除所有真实大小 1的冰山。由于真实大小 节点值 delta所以条件等价于节点值 1 - delta。这个技巧将全局修改的成本从O(N)降到了O(1)代价是我们在进行所有涉及节点值比较的操作如插入、删除、查询时都需要考虑delta的影响使用“真实大小”进行逻辑判断。2.3 为什么是Splay树有了delta处理全局加减我们还需要一个数据结构来处理动态的插入、删除和查询第k小。候选者通常有数组排序 删除和插入需要移动元素O(N)不可行。二叉搜索树BST 如果不平衡在极端数据下会退化成链表O(N)。红黑树如std::multiset 平衡性好支持插入、删除、查找第k小通过迭代器移动O(k)但对于本题频繁的按值域删除删除所有小于x的节点和查询第k小std::multiset的接口并不直接高效。按值域删除需要找到边界然后循环删除并非最优。权值线段树/树状数组 如果值域范围可以离散化且不大这是非常好的选择查询第k小是O(log V)。但本题冰山大小变化范围没有明确上限delta的累积可能使值域非常大离散化困难且动态扩展麻烦。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 deltadelta是一个全局变量。我们还需要一些全局变量和函数框架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 灵魂操作splaysplay(x, goal)函数是Splay树的灵魂它将节点x通过一系列旋转移动到goal节点的子节点位置通常goal0表示移动到根。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 // 注意如果分裂后树为空需要处理root0的情况 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是本题最易错、最需要小心处理的部分。让我们再仔细捋一遍delta - k。计算分裂键值split_key 1 - delta。这个值的意义是任何存储值相对值小于split_key的节点其真实值val delta都小于 1。调用split(split_key)。这个函数会修改全局root使其指向分裂后值 split_key的子树。同时它返回被分裂出来的、值 split_key的左子树的根。我们直接丢弃返回的左子树根节点。在内存池的实现中丢弃意味着我们不再关心这些节点它们占用的索引不会被回收简易实现中。在更严谨的实现中可以考虑内存回收但竞赛中通常不需要。分裂后root可能为空如果所有节点都被删除。后续操作需要判断root是否为空。一个致命的边界情况 当split_key大于树中所有值时split函数的行为是什么在我们的实现中find(split_key)会将最大值节点splay到根且该节点值 split_key。根据split函数逻辑会返回整个树的根并将root置为0。这是正确的意味着所有冰山都被删除。另一个边界 当split_key小于树中所有值时split会返回0左子树为空root保持不变。这意味着没有冰山被删除。确保你的split函数能正确处理这些情况。4.3 代码实现中的优化与技巧内存池与节点索引 使用数组tr和索引tot来管理节点比动态分配new Node()快得多也避免内存泄漏。long long类型 冰山大小、delta、操作值k都可能很大必须使用long long防止溢出。输入输出优化 使用scanf/printf而非cin/cout在大量数据读入时能显著提升性能。空树判断 在执行get_kth或splay操作前养成判断root是否为0的习惯。splay的摊还复杂度 虽然单次splay可能不是O(log N)但连续M次操作的总时间复杂度是O(M log N)可以放心使用。5. 常见问题、调试技巧与思维延伸即使理解了算法实现Splay树也常伴随着各种Bug。这里分享一些常见的坑和调试方法。5.1 常见问题速查表问题现象可能原因检查点与解决方案输出错误或随机值1. 没有使用long long导致溢出。2. 查询第k小时忘记加delta。3. 节点信息size维护错误。1. 检查所有与值相关的变量是否为long long。2. 在get_kth函数中确认返回的是val delta。3. 在rotate和insert后检查是否调用了pushup且顺序正确先更新子节点再更新父节点。程序运行超时1.splay操作写错导致死循环或退化。2. 分裂/合并操作逻辑错误使树不平衡。3. 输入输出未优化。1. 检查get(x)函数是否正确判断了左右孩子。2. 检查splay中的双旋条件 (get(x) get(y))。3. 对拍小数据观察树的高度是否增长异常。分裂操作后树状态异常1.split函数中指针切断和父节点更新有遗漏。2. 对find后根节点值与key的关系判断逻辑有误。1. 画图模拟分裂过程仔细检查每一步的fa和ch指针修改。2. 用一组简单数据如{1,3,5}测试分裂key2, key0, key6的情况打印树的结构。查询第k小结果不对1.size维护错误。2.get_kth中k的缩减逻辑错误。3. 存在重复元素(cnt1)时判断条件k left_size tr[cur].cnt写错。1. 在每次可能改变树结构的操作后打印根节点的size看是否符合预期。2. 单步调试get_kth观察k、left_size、cnt的变化。5.2 调试技巧编写打印函数 实现一个中序遍历打印树的函数以及一个打印节点详细信息的函数包括索引、值、左右孩子、父亲、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]); }小数据对拍 写一个暴力程序用vector模拟所有操作生成随机小数据N和M在20以内对比两个程序的最终结果和每次查询的结果。这是定位逻辑错误最有效的方法。单元测试 不要一下子写完整程序。先单独测试insert和get_kth不带delta再测试split功能最后整合delta和主逻辑。关注指针与索引 Splay树满是指针操作。确保在任何修改ch或fa的地方都同步更新对应节点的反向指针。例如tr[x].ch[1] y之后通常需要tr[y].fa x。5.3 思维延伸与优化删除节点的内存回收 上述实现中被split丢弃的节点索引没有被复用。在操作次数极多时可能导致tot超过MAXN。可以维护一个栈来回收删除的节点索引在insert时优先从栈中取索引。非旋转Treap (FHQ Treap) 作为替代 本题同样可以使用FHQ Treap解决其核心操作split和merge更为直观代码实现可能比Splay树更简短且同样高效。对于觉得Splay树旋转复杂的同学FHQ Treap是另一个绝佳选择。其split操作直接按值将树分成两棵完美契合本题需求。理解“摊还”复杂度 Splay树的单次操作复杂度可能不是严格的O(log N)但一系列操作的总时间是O(M log N)。这种“摊还”分析思想在算法竞赛中很重要像并查集路径压缩、向量动态数组(vector)的扩容都是摊还复杂度的例子。攻克“冰山”这道题其意义远不止于通过一次比赛。它强迫你深入理解一种强大的、灵活的数据结构并掌握“懒惰标记”这种将全局修改转化为局部判断的经典思想。当你再遇到需要维护动态序列、支持区间操作和快速查询的问题时你会想起来你工具箱里还有Splay树这把瑞士军刀。实现过程中调试的煎熬最终都会转化为对指针、递归、树形结构更深的理解。