从洛谷P2234看平衡树实战：STL set与手写Treap解决动态查询

1. 项目概述：从一道题看数据结构的实战价值

最近在洛谷上刷题，又遇到了老朋友 P2234 “营业额统计”。这道题别看它来自2002年的 HNOI（湖南省队选拔），题目描述也带着点“古早味”，但它在算法竞赛圈子里，尤其是对于正在学习数据结构的同学来说，绝对是一道绕不开的经典。为什么？因为它把一个看似是数学统计的问题，巧妙地转化为了一个对数据结构基本功的极致考验。题目要求我们计算公司每天营业额的最小波动值之和，这个“最小波动值”的定义是：当天营业额与之前所有天营业额中，差值绝对值最小的那个。换句话说，对于第i天的营业额a[i]，我们需要在a[1]到a[i-1]这个历史数据集合里，找到与a[i]最接近的那个数（前驱或后继）。

你可能会想，这不就是遍历一下前面i-1个数，找最小差值吗？如果n最大是 32767，最坏情况下的时间复杂度是 O(n²)，那可是超过 10^9 次运算，妥妥地超时。所以，这道题的核心挑战在于：如何高效地在一个动态增长的集合中，为每一个新加入的元素，快速找到与其最接近的值。这正是平衡二叉搜索树（BST）的拿手好戏。今天，我就结合自己多次实现和调试这道题的经验，用 C++ 带你从零开始，不仅把这道题 AC 了，更要弄明白背后的数据结构选型、实现细节以及那些容易踩坑的地方。无论你是刚学完 STLset想练练手，还是打算手搓一个平衡树来加深理解，这篇文章都会给你带来实实在在的收获。

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

2.1 问题本质与暴力解法的局限性

我们先彻底吃透题意。设第i天的营业额为val，我们需要计算min(|val - a[j]|)，其中j从 1 到i-1。这个“最小绝对差值”，等价于在历史数据集合S中寻找val的前驱（小于等于val的最大值）和后继（大于等于val的最小值）。然后，最小波动值就是min(val - 前驱, 后继 - val)。第一天没有历史数据，按照定义，其最小波动值就是它自身的营业额。

最直接的暴力方法就是模拟这个过程：用一个数组记录所有历史营业额。对于第i天，遍历数组的前i-1个元素，更新最小差值。代码简单，但复杂度为 O(n²)。代入n=32767，计算量级约为 5.3 亿次比较和绝对值运算，在典型的竞赛时间限制（1秒）内是绝对无法通过的。这就迫使我们寻找更优的数据结构。

2.2 平衡二叉搜索树：为何是唯一正解？

我们需要一个数据结构，支持以下两种核心操作：

1. 插入（Insert）：将第i天的营业额加入集合。
2. 查询前驱/后继（Predecessor/Successor）：在当前的集合中，快速找到与给定值最接近的两个数。

二叉搜索树（BST）天生就是为了这种“动态有序集合”的查找而生的。在理想情况下（树是平衡的），插入和查找的时间复杂度都是 O(log n)。对于本题，n=32767，log2(32767) ≈ 15，总时间复杂度约为 O(n log n)，完全在可接受范围内。

但是，普通的 BST 有一个致命弱点：如果输入数据是有序的（比如营业额单调递增或递减），BST 会退化成一条链，深度变为n，时间复杂度退化回 O(n²)，和暴力法没有区别。题目虽然没有明确说明数据是否有序，但我们必须考虑最坏情况。因此，我们需要能保持平衡的二叉搜索树，即平衡二叉搜索树。

注意：很多同学第一次做这道题，知道要用“树”，但忽略了“平衡”二字，自己实现了一个普通 BST，结果提交后有几个测试点超时，就是因为数据可能存在有序或近似有序的情况。

2.3 C++实现方案对比：STL set 与手写平衡树

对于竞赛和实践，我们主要有两种实现路径：

方案一：使用 C++ STL 中的setstd::set是基于红黑树（一种自平衡二叉搜索树）实现的，它自动维护树的平衡，提供了insert,lower_bound,upper_bound等成员函数，可以非常方便地找到前驱和后继。

• 优点：代码极其简洁，不易出错，开发效率高。
• 缺点：set的迭代器操作需要小心（特别是处理边界情况），并且由于其封装性，对树内部结构的理解帮助有限。lower_bound返回的是大于等于给定值的迭代器，要找到严格小于给定值的前驱，需要稍微绕一下。

方案二：手写平衡树（如 Treap, Splay, AVL）手动实现一个平衡树数据结构。

• 优点：对数据结构的理解提升巨大，可以完全掌控所有操作，并且能处理更复杂的问题（比如区间操作、名次树等，set无法直接完成）。
• 缺点：代码量大，调试复杂，容易写错。

对于本题，我强烈推荐初学者和希望快速 AC 的同学使用std::set。它的性能完全足够，且代码量可能只有手写树的十分之一。本文也将以set的实现作为主线进行详解，并在最后部分探讨手写 Treap 的思路，供学有余力的同学参考。

3. 基于 STL set 的详细实现与代码解析

3.1 算法流程设计

使用set解决本题的步骤非常清晰：

1. 初始化一个空的set<int>用于存储历史营业额，初始化总和ans = 0。
2. 读入总天数n。
3. 读入第一天的营业额first_val。根据题意，第一天的最小波动值就是其本身，所以ans += first_val，并将first_val插入set。
4. 对于第2天到第n天： a. 读入当前营业额val。 b. 在set中寻找val的后继：使用set.lower_bound(val)，它返回指向第一个不小于val的元素的迭代器。 c. 在set中寻找val的前驱：后继的迭代器it的前一个位置（--it）可能就是前驱。但需要仔细处理边界条件。 d. 计算当前最小波动值delta：分别计算val与找到的前驱、后继的差值绝对值（如果存在），取最小值。 e. 将delta累加到ans。 f. 将val插入set，供后续天数查询。
5. 输出ans。

3.2 关键操作：如何准确找到前驱和后继？

这是实现的核心，也是容易出错的地方。我们需要考虑几种边界情况：

• 集合为空：这只发生在第一天，我们已经特殊处理。
• val在集合中已存在：此时最小波动值为 0。lower_bound(val)会返回指向这个val的迭代器，它既是“后继”（大于等于），我们也可以用它找到前驱（需要判断）。
• val比集合中所有数都小：此时lower_bound(val)返回set.begin()，即最小的元素，它是val的后继。val没有严格意义上的前驱（因为前驱应该小于val）。
• val比集合中所有数都大：此时lower_bound(val)返回set.end()，这是一个尾后迭代器，不能解引用。val的前驱是集合中的最大元素。

具体代码逻辑如下：

#include <iostream> #include <set> #include <climits> // 用于 INT_MAX #include <cmath> // 用于 abs using namespace std; int main() { int n; cin >> n; set<int> company; int first_val; cin >> first_val; long long ans = first_val; // 注意用 long long 防止溢出 company.insert(first_val); for (int i = 2; i <= n; ++i) { int val; cin >> val; // 寻找后继：第一个 >= val 的数 auto it_succ = company.lower_bound(val); // 初始化最小差值为一个很大的数 int delta = INT_MAX; // 情况1：找到了后继 (it_succ != company.end()) if (it_succ != company.end()) { delta = min(delta, abs(*it_succ - val)); } // 情况2：寻找前驱。前驱是第一个 < val 的数，即 it_succ 的前一个位置 // 如果 it_succ 指向 begin()，则没有前驱 if (it_succ != company.begin()) { auto it_pred = prev(it_succ); // 等同于 --it_succ，但更安全 delta = min(delta, abs(*it_pred - val)); } // 注意：如果 val 本身在集合中，那么 it_succ 指向 val， // it_pred 指向比 val 小的最大数，delta 通过 min 比较会得到 0。 ans += delta; company.insert(val); } cout << ans << endl; return 0; }

3.3 代码逐行解读与易错点分析

1. 数据类型与溢出：结果保证小于2^31，但我们在累加过程中使用int可能在中途溢出。因此ans应使用long long。这是竞赛中非常常见的陷阱。
2. lower_bound的使用：set.lower_bound(val)是成员函数，时间复杂度为 O(log n)。不要误用全局的std::lower_bound(set.begin(), set.end(), val)，那样是线性复杂度 O(n)。
3. 迭代器边界检查：解引用set.end()或--set.begin()是未定义行为，会导致运行时错误。因此在使用*it前，必须判断it != company.end()；在执行--it或prev(it)前，必须判断it != company.begin()。
4. prev函数：prev(it_succ)是 C++11 中的标准库函数，返回it_succ前一个位置的迭代器。它比直接写--it_succ更清晰，且it_succ本身不会被改变。如果改变了it_succ，可能会影响后续对后继的判断。
5. 重复元素处理：set本身不允许重复元素。如果某天营业额和之前某天完全相同，company.insert(val)不会插入新元素，但返回的 pair 中 second 为 false。不过这对我们的算法没有影响，因为我们在插入前已经计算完了当天的波动值。即使集合中已存在val，lower_bound会指向它，delta计算结果为 0，完全正确。

实操心得：在写这类涉及迭代器操作的代码时，我习惯先用笔画一下几种边界情况（最大、最小、相等），然后对照代码看每个分支是否被正确处理。这种“脑内调试”能避免很多低级错误。

4. 性能分析与扩展：面对更大数据的思考

我们的set解法时间复杂度为 O(n log n)，空间复杂度 O(n)。对于本题的 n≤32767 游刃有余。即使在常见的 1秒 时限下，也完全足够。

但我们可以思考一下，如果数据量扩大到n ≤ 10^6甚至更大，O(n log n)依然高效吗？理论上，log2(10^6) ≈ 20，运算量级在千万次，配合现代 CPU 通常可以在 1 秒内完成。但常数因子很重要。std::set由于红黑树的复杂旋转操作和节点内存非连续，其常数比数组结构大。在极端追求性能的场景（例如n=10^7），我们可能会考虑其他数据结构：

• 手写 Treap (树堆)：基于随机化的平衡 BST，代码比红黑树简单，平均效率很高，且常数较小。
• 手写 Splay (伸展树)：同样可以实现，并且有“局部性”的特点，访问过的节点会被提到根部，对于某些访问模式有奇效。
• 离线处理 + 排序 + 二分：如果所有数据已知（离线），我们可以先全部读入，然后进行排序。对于第i天的数据，在排序后的前i-1个数据中二分查找前驱后继。但这需要维护一个有序列表并支持快速插入，用数组实现插入是 O(n) 的，反而更慢。可以使用块状链表或树状数组+离散化来优化，但思维复杂度陡增。

对于本题和绝大多数竞赛场景，std::set是最佳选择，在简洁性、可靠性和性能之间取得了完美平衡。

5. 从 set 到手写 Treap：深入数据结构内部

为了更深刻地理解平衡树是如何工作的，我们尝试手写一个 Treap 来解决本题。Treap 是 Tree 和 Heap 的结合，每个节点除了键值key（营业额），还有一个随机生成的优先级priority。它同时满足二叉搜索树（左子树所有键值 < 根节点键值 < 右子树所有键值）和堆（根节点优先级高于子节点优先级）的性质。通过随机化的优先级，Treap 能以很高的概率保持平衡。

5.1 Treap 节点设计与核心操作

我们首先定义节点结构体，并实现左右旋操作来维护堆性质。

#include <iostream> #include <cstdlib> #include <climits> #include <cmath> using namespace std; struct Node { int key; // 营业额 int priority; // 随机优先级 Node *left, *right; Node(int val) : key(val), priority(rand()), left(nullptr), right(nullptr) {} }; // 右旋 (以y为根) void rightRotate(Node* &y) { Node* x = y->left; y->left = x->right; x->right = y; y = x; // 更新根节点 } // 左旋 (以x为根) void leftRotate(Node* &x) { Node* y = x->right; x->right = y->left; y->left = x; x = y; // 更新根节点 }

5.2 Treap 的插入与查找前驱后继

插入操作是 Treap 的核心。它先像普通 BST 一样递归插入到叶子节点，然后通过旋转（左旋/右旋）将新节点“上浮”，直到其优先级满足堆的性质。

// 插入键值 key void insert(Node* &root, int key) { if (root == nullptr) { root = new Node(key); return; } if (key < root->key) { insert(root->left, key); // 如果左子节点的优先级更大，需要右旋 if (root->left->priority > root->priority) { rightRotate(root); } } else { // 允许重复键值？本题可以，但通常Treap不允许。我们这里假设无重复，或重复时波动为0，插入与否不影响。 insert(root->right, key); // 如果右子节点的优先级更大，需要左旋 if (root->right->priority > root->priority) { leftRotate(root); } } }

查找前驱和后继的逻辑与 BST 一致：

• 前驱：从根开始，如果当前节点键值>= key，则向左子树找；否则，用当前节点更新答案，并向右子树找。
• 后继：从根开始，如果当前节点键值<= key，则向右子树找；否则，用当前节点更新答案，并向左子树找。

// 查找小于 key 的最大值（前驱） int findPredecessor(Node* root, int key) { int pred = INT_MIN; // 用一个很小的数初始化 while (root != nullptr) { if (root->key < key) { pred = root->key; // 当前节点是候选 root = root->right; // 尝试找更大的（但依然小于key） } else { root = root->left; // 当前节点太大，向左找更小的 } } return pred; } // 查找大于 key 的最小值（后继） int findSuccessor(Node* root, int key) { int succ = INT_MAX; // 用一个很大的数初始化 while (root != nullptr) { if (root->key > key) { succ = root->key; // 当前节点是候选 root = root->left; // 尝试找更小的（但依然大于key） } else { root = root->right; // 当前节点太小，向右找更大的 } } return succ; }

5.3 基于 Treap 的完整解题代码

将上述部分组合起来，并注意内存管理（本题可以省略，程序结束即释放）。

#include <iostream> #include <cstdlib> #include <climits> #include <cmath> using namespace std; struct Node { /* 同上 */ }; void rightRotate(Node* &y) { /* 同上 */ } void leftRotate(Node* &x) { /* 同上 */ } void insert(Node* &root, int key) { /* 同上 */ } int findPredecessor(Node* root, int key) { /* 同上 */ } int findSuccessor(Node* root, int key) { /* 同上 */ } int main() { srand(time(0)); // 初始化随机种子 int n; cin >> n; Node* root = nullptr; int first_val; cin >> first_val; long long ans = first_val; insert(root, first_val); for (int i = 2; i <= n; ++i) { int val; cin >> val; int pred = findPredecessor(root, val); int succ = findSuccessor(root, val); int delta = INT_MAX; if (pred != INT_MIN) { // 前驱存在 delta = min(delta, abs(val - pred)); } if (succ != INT_MAX) { // 后继存在 delta = min(delta, abs(succ - val)); } // 如果 val 已在树中，pred 和 succ 至少有一个等于 val，delta 会被更新为 0。 ans += delta; insert(root, val); } cout << ans << endl; // 实际应用中应添加销毁树的代码释放内存 return 0; }

注意事项：手写 Treap 需要注意几个关键点。一是随机数种子srand最好用time(0)，但注意在多次调用时不要重复初始化。二是递归插入的旋转操作一定要更新引用(Node* &root)，确保旋转后父节点能指向新的子根。三是查找前驱后继的 while 循环条件，以及用INT_MIN/INT_MAX来标识不存在的情况。调试手写树时，建议先写一个中序遍历函数打印树结构，验证插入是否正确。

6. 常见问题与调试技巧实录

即使思路清晰，实现这道题时还是会遇到一些典型的“坑”。下面是我和许多同学在实战中遇到过的问题及解决方法。

Q1: 使用set的代码样例过了，但提交后 WA (Wrong Answer)。

• 检查点1：第一天的处理。题目明确说“第一天的最小波动值为第一天的营业额”。你的代码是否直接将第一个数加到了总和里？是否在计算第二天波动值前才插入第一个数？顺序错误会导致第一天被错误地当作历史数据查询。
• 检查点2：ans的数据类型。虽然结果保证小于2^31，但中间累加过程可能溢出int范围。务必使用long long。
• 检查点3：前驱后继的边界条件。当val是集合中最小或最大时，你的delta计算是否正确？例如，如果只有后继没有前驱，delta应该等于后继 - val，而不是某个初始值。我的代码中通过INT_MAX初始化和条件判断来处理。
• 检查点4：输入输出。确保使用cin/cout或scanf/printf一致。在大量数据输入时，可以加入ios::sync_with_stdio(false); cin.tie(0);来加速cin/cout。

Q2: 手写 Treap 编译通过，但运行结果不对或程序崩溃。

• 检查点1：指针未初始化。新建节点时，left和right指针是否初始化为nullptr？
• 检查点2：旋转操作写错。这是最易错的地方。画图！对照着图检查左右旋代码中指针的重新指向顺序。确保旋转后树的二叉搜索树性质不变。
• 检查点3：递归插入的引用传递。insert(Node* &root, ...)中的&至关重要，它确保了对根节点指针的修改能传递回上一层。如果漏了&，旋转就白做了。
• 检查点4：查找前驱后继的逻辑。用一组简单数据（如[5, 1, 2]）手动模拟，看你的findPredecessor和findSuccessor函数返回的值是否正确。

Q3: 程序超时 (TLE)。

• 对于set解法：几乎不可能超时。如果超时，检查是否错误地使用了全局std::lower_bound而不是成员函数set::lower_bound。
• 对于手写树解法：大概率是树的平衡性出了问题，退化成链。检查插入逻辑和旋转条件是否正确。确保优先级是随机的（srand已调用）。可以尝试输出树的高度来验证。

调试技巧：

1. 小数据对拍：写一个暴力求解的程序（O(n²)），用随机生成的小数据（n=10）运行两个程序，对比结果。这是查找逻辑错误最有效的方法。
2. 打印中间状态：在set版本中，可以在每次插入后打印set的内容（用迭代器遍历）。在手写树版本中，实现一个中序遍历函数inorderPrint，打印每个节点的 key 和 priority，观察树的结构是否平衡。
3. 使用调试器：在关键函数（如旋转、插入）处设置断点，单步执行，观察变量值的变化是否符合预期。

这道“营业额统计”题，就像一位严格的教练，它用看似简单的需求，逼着我们去理解并应用“动态有序集合查询”这一核心思想。无论是选择 STLset的“巧劲”，还是挑战手写平衡树的“硬功”，这个过程本身对编程能力的提升都是实实在在的。最后，关于代码风格，我个人的习惯是，在竞赛中追求速度就用set，在平时练习想夯实基础就手写 Treap。把这两种实现都掌握，以后再遇到类似问题，你就能真正做到心里有底，手上有招了。