1. 项目概述从“贪婪大陆”到线段树实战最近在信奥信息学奥林匹克的刷题社区里看到不少朋友在讨论P2184“贪婪大陆”这道题。题目名字听起来挺有意思但点进去一看往往就被它“区间修改、区间查询”的外衣给唬住了。很多初学者尤其是刚接触C和数据结构不久的同学一看到题目描述里又是地雷又是询问的容易直接想到暴力模拟结果一提交就是时间超限。其实这道题是练习线段树Segment Tree的一个绝佳模板它完美诠释了如何用这种数据结构高效处理一类特定的区间问题。今天我就结合自己当年踩坑和后来教学的经验带大家用C从头实现一遍不仅把题AC了更要把线段树处理这类问题的核心思想掰开揉碎了讲清楚。简单来说P2184“贪婪大陆”描述了一个战场场景我们需要维护一条战线一个长度为N的序列支持两种操作。第一种操作是在一个区间[L, R]内部署一种特定类型的地雷。第二种操作是询问一个区间[L, R]内有多少种不同类型的地雷。注意这里的关键词是“种数”而不是地雷的总数。这意味着即使你在[1, 3]区间布了10颗A型雷在[2, 4]区间布了10颗B型雷询问[2, 3]区间时答案应该是2有两种雷A和B而不是20。这个“种类数”的统计需求是这道题区别于普通区间和查询的核心也是我们设计数据结构的出发点。2. 核心思路解析为什么线段树是正解2.1 暴力模拟的局限性分析拿到题目最直观的想法就是模拟。我们可以开一个二维数组mine[i][j]来表示第i个位置是否有第j种地雷。每次布设操作就在区间[L, R]内对一种新的地雷类型标记为存在。查询时就遍历区间[L, R]统计出现过哪些不同的地雷类型。这种方法的复杂度是多少呢假设操作总数为M序列长度为N地雷类型最多可能有M种每次布设都可能是一种新类型。那么一次布设操作是O(N)的复杂度需要遍历区间标记。一次查询操作在最坏情况下是O(N * M)的复杂度遍历区间每个位置并检查所有M种类型是否出现过。显然当N和M达到10^5级别时这样的复杂度是完全无法接受的必然超时。注意这里是一个典型的思维陷阱。很多初学者会想“我开个vectorset或者map来存每个位置的地雷种类查询时合并集合”。这虽然比二维数组好但合并区间内所有位置的集合复杂度依然很高本质上没有解决根本问题。我们需要换一个角度思考。2.2 转化问题从“位置视角”到“区间视角”让我们跳出“每个位置有什么雷”的思维定式。题目问的是区间内地雷的种类数。一种地雷只要它的布设区间与我们的查询区间有交集那么这种雷就应该被计入答案。换句话说对于一次查询[L, R]一种特定的地雷是否被计入取决于历史上是否有一次布设操作(l, r)满足[l, r]与[L, R]有交集即不是完全不相交。这等价于不是r L该地雷区间完全在查询区间左边也不是l R该地雷区间完全在查询区间右边。因此我们可以这样转化区间[L, R]内的地雷种类数 历史上所有布设操作的总数 - 那些布设区间完全在[L, R]左侧的操作数 - 那些布设区间完全在[L, R]右侧的操作数。这个转化是本题最精妙的地方。我们不再需要关心具体哪个位置有哪些雷而是关心“布设操作”这个事件本身。定义total从开始到当前总共发生了多少次布设操作。left_count(x)布设区间的右端点r小于x的操作数量。即完全在x左侧的操作数。right_count(x)布设区间的左端点l大于x的操作数量。即完全在x右侧的操作数。那么对于查询区间[L, R]完全在其左侧的操作数就是left_count(L)。完全在其右侧的操作数就是right_count(R)。因此答案ans total - left_count(L) - right_count(R)。2.3 数据结构选型线段树如何登场经过上述转化问题变成了我们需要动态维护一个变量total每次布设操作加1即可。我们需要高效地查询有多少次操作的右端点 L以及有多少次操作的左端点 R。这本质上是对两个序列所有操作的左端点序列、所有操作的右端点序列进行动态单点更新增加一个点和前缀/后缀和查询。对于“右端点 L”的查询等价于对右端点序列查询下标在[1, L-1]区间内的元素个数即前缀和。对于“左端点 R”的查询等价于对左端点序列查询下标在[R1, N]区间内的元素个数即后缀和。也可以转化为total - 前缀和(R)但直接维护后缀和逻辑更清晰。线段树正是处理动态区间和问题的利器。我们可以维护两棵线段树树R维护右端点的分布。update(r, 1)表示在位置r增加一个右端点即发生了一次布设其右端点为r。query(1, L-1)就是完全在L左侧的操作数。树L维护左端点的分布。update(l, 1)表示在位置l增加一个左端点。query(R1, N)就是完全在R右侧的操作数。这样每次布设操作(l, r)我们执行total。treeL.update(l, 1)。treeR.update(r, 1)。每次查询操作[L, R]我们计算ans total - treeR.query(1, L-1) - treeL.query(R1, N)。时间复杂度每次操作都是O(log N)完美解决。3. C实现与代码逐行精讲理解了核心思路我们开始动手用C实现。这里会采用经典的静态数组实现线段树结构清晰效率也高。3.1 数据结构定义与全局变量#include iostream using namespace std; const int MAXN 100005; // 根据题目要求N最大为10^5 const int MAXM 4 * MAXN; // 线段树数组大小通常开4倍原数组大小 // 线段树结构体 struct SegmentTree { int sum[MAXM]; // 存储区间和 // 递归建树本题初始值全为0所以建树过程可以简化甚至省略 void build(int node, int left, int right) { sum[node] 0; if (left right) return; // 叶子节点 int mid (left right) 1; build(node 1, left, mid); // 左儿子 build(node 1 | 1, mid 1, right); // 右儿子 } // 单点更新在位置pos增加值val void update(int node, int left, int right, int pos, int val) { if (left right) { sum[node] val; return; } int mid (left right) 1; if (pos mid) { update(node 1, left, mid, pos, val); } else { update(node 1 | 1, mid 1, right, pos, val); } // 向上更新父节点区间和 sum[node] sum[node 1] sum[node 1 | 1]; } // 区间查询查询区间[ql, qr]的和 int query(int node, int left, int right, int ql, int qr) { if (ql qr) return 0; // 重要查询区间非法时直接返回0 if (ql left right qr) { return sum[node]; } int mid (left right) 1; int result 0; if (ql mid) { result query(node 1, left, mid, ql, qr); } if (qr mid) { result query(node 1 | 1, mid 1, right, ql, qr); } return result; } }; SegmentTree treeL, treeR; // 分别维护左端点、右端点的线段树 int total 0; // 总操作数 int N, M; // N为战线长度M为指令数关键点解析const int MAXM 4 * MAXN;这是线段树开数组的经验值。一棵完全二叉树最坏情况下的节点数大约是叶子节点的4倍。开3倍有时可能不够4倍是安全的。build函数本题初始所有位置计数为0所以build函数只是初始化数组为0。在实际代码中我们甚至可以省略显式的建树过程直接在全局定义sum数组默认初始值就是0。但保留这个结构有助于理解线段树的完整操作。update函数标准的单点更新。pos是位置左端点或右端点的值val是增加量本题中val始终为1。query函数标准的区间和查询。特别注意边界判断if (ql qr) return 0;。在查询treeR.query(1, L-1)时如果L1那么查询区间是[1, 0]这是非法的必须直接返回0。这是实现中非常容易忽略的一个细节会导致递归无法终止或结果错误。3.2 主逻辑与输入输出处理int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 关闭同步加速C的输入输出对于大量数据至关重要 cin N M; // treeL.build(1, 1, N); // 可以显式建树但初始值为0可省略 // treeR.build(1, 1, N); for (int i 0; i M; i) { int op, l, r; cin op l r; if (op 1) { // 布设操作 total; treeL.update(1, 1, N, l, 1); // 在左端点l处计数1 treeR.update(1, 1, N, r, 1); // 在右端点r处计数1 } else if (op 2) { // 查询操作 // 完全在左侧的操作数右端点 l - 查询 treeR 的 [1, l-1] int leftCount treeR.query(1, 1, N, 1, l - 1); // 完全在右侧的操作数左端点 r - 查询 treeL 的 [r1, N] int rightCount treeL.query(1, 1, N, r 1, N); // 答案 总数 - 完全左 - 完全右 int ans total - leftCount - rightCount; cout ans \n; } } return 0; }关键点解析ios::sync_with_stdio(false); cin.tie(nullptr);这是C做算法题几乎必备的“加速语句”。它解除了C标准流cin/cout与C标准流scanf/printf的同步并解除了cin和cout之间的绑定可以大幅提升输入输出效率避免因IO导致超时。操作类型判断根据输入的op执行不同逻辑清晰明了。查询计算完全对应了我们推导出的公式。注意查询的区间范围特别是当l1或rN时l-1和r1会越界但我们的query函数已经通过if (ql qr) return 0;处理了这种情况。输出使用cout ans \n;。用\n而不是endl因为endl会刷新缓冲区导致额外的性能开销。3.3 完整可运行代码整合将以上所有部分整合得到完整的AC代码#include iostream using namespace std; const int MAXN 100005; const int MAXM 4 * MAXN; struct SegmentTree { int sum[MAXM]; void update(int node, int left, int right, int pos, int val) { if (left right) { sum[node] val; return; } int mid (left right) 1; if (pos mid) { update(node 1, left, mid, pos, val); } else { update(node 1 | 1, mid 1, right, pos, val); } sum[node] sum[node 1] sum[node 1 | 1]; } int query(int node, int left, int right, int ql, int qr) { if (ql qr) return 0; // 关键 if (ql left right qr) { return sum[node]; } int mid (left right) 1; int result 0; if (ql mid) { result query(node 1, left, mid, ql, qr); } if (qr mid) { result query(node 1 | 1, mid 1, right, ql, qr); } return result; } }; SegmentTree treeL, treeR; int total 0; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; for (int i 0; i M; i) { int op, l, r; cin op l r; if (op 1) { total; treeL.update(1, 1, N, l, 1); treeR.update(1, 1, N, r, 1); } else { int leftCount treeR.query(1, 1, N, 1, l - 1); int rightCount treeL.query(1, 1, N, r 1, N); int ans total - leftCount - rightCount; cout ans \n; } } return 0; }4. 深度剖析线段树在此类问题中的通用性P2184“贪婪大陆”的解法揭示了一类区间统计问题的通用思路。当问题可以转化为“统计与查询区间有交集的区间事件的数量”时我们都可以考虑使用类似的“左右端点分别维护”的线段树模型。4.1 模型抽象与扩展我们可以把这个模型抽象出来事件一个区间[l, r]。查询给定区间[L, R]问有多少个事件区间与之有交集。核心公式有交集的事件数 总事件数 - 完全在左边的事件数 - 完全在右边的事件数。数据结构用两棵线段树或树状数组分别维护所有事件左端点l的分布、右端点r的分布。操作新增事件[l, r]totaltreeL.add(l, 1)treeR.add(r, 1)。查询区间[L, R]ans total - treeR.query(1, L-1) - treeL.query(R1, N)。这个模型非常强大。例如它可以用来解决实时统计在线用户每个用户的登录-登出视为一个区间事件查询某个时间段内有多少不同的用户在线。日程冲突检测每个日程是一个区间快速查询某个时间段内有多少个已安排的日程即有多少个日程与之有交集。4.2 线段树与树状数组的抉择在上面的实现中我们使用了线段树。实际上由于我们只进行单点更新和区间求和这是一个标准的“前缀和”动态维护问题完全可以用更简洁、常数更小的**树状数组Binary Indexed Tree, BIT**来实现。树状数组的代码量更少运行更快。下面是使用两个树状数组的核心代码对比// 树状数组实现 int bitL[MAXN], bitR[MAXN]; int N; inline int lowbit(int x) { return x -x; } void add(int bit[], int idx, int val) { while (idx N) { bit[idx] val; idx lowbit(idx); } } int prefix_sum(int bit[], int idx) { int res 0; while (idx 0) { res bit[idx]; idx - lowbit(idx); } return res; } int range_sum(int bit[], int l, int r) { if (l r) return 0; return prefix_sum(bit, r) - prefix_sum(bit, l - 1); } // 主逻辑中的更新和查询 // 布设操作 add(bitL, l, 1); add(bitR, r, 1); total; // 查询操作 int leftCount prefix_sum(bitR, l - 1); // 右端点 l int rightCount total - prefix_sum(bitL, r); // 左端点 r 用总数减去前缀和(r) int ans total - leftCount - rightCount;可以看到树状数组的代码更加简洁。在信奥竞赛中对于此类纯单点更新、区间求和的问题优先考虑树状数组因为它编写不易出错且效率更高。线段树则更通用能处理区间更新、区间最值等更复杂的问题。理解两者在这道题上的等价性对于灵活运用数据结构至关重要。5. 常见错误与调试技巧实录即便思路清晰在实现时也难免会遇到各种问题。下面是我在初学以及教学过程中看到同学们最容易踩的几个坑。5.1 数组大小开不够这是最经典的错误之一。题目说N最大为100000。如果线段树数组只开MAXN即100005大小是远远不够的。线段树需要大约4倍的空间。开成4 * MAXN是安全且常见的做法。树状数组只需要开N5即可。症状程序在本地运行小数据正常提交到OJ在线判题系统后出现“运行时错误”Runtime Error, RE特别是“段错误”Segmentation Fault。排查首先检查所有数组的大小是否足够。对于线段树确保是4*N级别。5.2 查询区间边界判断错误这是我们代码中特别强调的if (ql qr) return 0;。当查询[1, L-1]而L1时区间变为[1, 0]。如果不加判断递归函数会陷入混乱例如mid (10)1 0导致后续计算下标错误或无限递归。症状程序可能输出错误答案或者在特定输入下如第一次查询就是[1, x]直接崩溃。排查在query函数的开头务必加上非法区间判断。这是一个非常好的编程习惯。5.3 数据类型溢出虽然本题的计数操作次数M也在10^5级别total和线段树节点值用int足够。但在一些变体问题或者习惯性使用long long更安全。如果题目数据范围更大int可能溢出。症状计算结果出现负数或异常大的正数。排查养成根据数据范围选择数据类型的习惯。如果总操作数可能超过2×10^9就使用long long。在不确定时对于求和、计数类变量使用long long是更稳妥的选择。5.4 输入输出效率导致超时当M很大例如10^5时使用未加速的cin/cout或者滥用endl很容易导致输入输出成为性能瓶颈造成“时间超限”Time Limit Exceeded, TLE。症状算法复杂度正确但就是超时。排查与解决务必在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);。输出换行时使用\n而不是endl。如果还是卡常可以考虑使用C风格的scanf和printf它们通常更快。5.5 线段树递归函数参数传递错误在写递归的update和query函数时混淆了node当前节点编号、left/right当前节点表示的区间、pos/ql/qr更新/查询的目标位置或区间这几个参数。症状程序逻辑混乱结果完全不对。排查给变量起有意义的名字如curNode,curL,curR,targetPos,queryL,queryR。在纸上画出一个简单的线段树结构模拟递归过程有助于理解。6. 性能分析与优化空间我们实现的线段树解法每次操作更新或查询时间复杂度为O(log N)其中N是序列长度战线长度。对于M次操作总时间复杂度为O(M log N)在N和M为10^5时完全可行。空间复杂度上我们开了两个大小为4*MAXN的int数组大约占用2 * 4 * 100000 * 4 bytes ≈ 3.2 MB内存消耗也很小。进一步优化思路非递归线段树zkw线段树递归调用有函数栈开销。有一种自底向上的线段树实现zkw线段树常数更小代码也更短适合竞赛追求极致速度。但对于理解和面试掌握递归版本更为重要。离散化如果题目中的“位置”范围非常大例如1到10^9但操作次数M相对较少10^5我们就不能直接开那么大的数组了。这时需要先将所有出现过的左端点、右端点坐标收集起来排序去重映射到1~K的范围内K≤2M然后再用线段树或树状数组维护。这就是“离散化”技巧。P2184的N本身不大所以不需要。但这是一个非常重要的进阶技巧。树状数组替代如前所述用树状数组代码更优。在竞赛中对于单点更新、区间求和树状数组是首选。7. 举一反三相关题目推荐彻底弄懂“贪婪大陆”后可以尝试解决以下类似或进阶题目巩固线段树/树状数组的应用能力P3368 【模板】树状数组 2练习树状数组的区间修改、单点查询需要引入差分思想。P3372 【模板】线段树 1练习线段树的区间修改加、区间查询和需要用到懒惰标记Lazy Tag。P3373 【模板】线段树 2线段树懒惰标记的进阶版同时存在加法和乘法两种操作对懒惰标记的下传顺序有要求。P1908 逆序对可以用树状数组或归并排序求解是树状数组的经典应用题。LOJ 或 Codeforces 上关于“区间染色种类数”的题目这类问题有时被称为“颜色段问题”可能需要更复杂的线段树节点设计来维护是“贪婪大陆”思想的深度拓展。刷题的关键不在于数量而在于深度。把一道像P2184这样的经典题吃透理解其背后的模型转化和数据结构思想远比盲目刷很多题更有效。当你再遇到“统计区间内不同元素个数”或者“统计与查询区间有交集的事件”这类问题时你就能立刻联想到“左右端点分离统计”的妙招这才是信奥刷题带给我们的真正能力提升。