离散化详解：从原理到C++实现与竞赛实战

1. 离散化到底在解决什么问题1.1 先从一道让人头大的题说起如果你参加过CSP-S或者刷过近几年的真题应该见过这种场景题目里给你一段区间起点终点都给到1e9然后让你统计覆盖次数、区间长度、重叠部分之类的东西。数据量看着不大可能就1e5条操作但坐标一上来就是0到1e9开数组直接原地爆炸——int a[1000000001]这种事在竞赛里是绝对不可能干的。我第一次遇到这种题的时候也愣了半天心想这不是逼着我用map吗后来发现map能过一部分题但在需要连续区间操作、或者要跑线段树的时候map的常数能把你卡到怀疑人生。这时候就需要离散化出场了。离散化的核心想法一句话就能说清楚我们真正关心的不是坐标本身有多大而是这些坐标之间的相对顺序关系。就像你在排队你不需要知道队伍到底排了多长只需要知道谁在谁前面。把巨大的坐标值映射成连续的、紧凑的整数编号这就是离散化。这玩意儿在CSP-S里的地位很特殊它本身不单独出大题但几乎无处不在。线段树、树状数组、扫描线、区间DP、离线查询这些高频考点里但凡遇到坐标范围大而点数少的情况十有八九要先用离散化把数据“压扁”。你离散化写得熟不熟直接决定了后面那些高级数据结构能不能顺利跑起来。1.2 它和“哈希”有什么区别很多初学者会把离散化和哈希搞混觉得都是“把大数映射成小数”。确实有相似之处但思路完全不同。哈希追求的是把一个对象映射到一个随机分布的地址上映射前后顺序关系通常不保留而离散化追求的恰恰是保序——原来的a b离散化之后依然满足id(a) id(b)。保序这个性质在竞赛里极其关键。因为线段树、树状数组这些数据结构本质上都是按照“位置”来组织的数据结构它们依赖的只是下标之间有大小关系不关心下标具体是3还是3000000。只要相对位置不变所有基于下标的操作都能照常进行。我习惯用一个生活化的例子给学生讲把考试成绩映射成排名。张三考了97分李四考了88分王五考了97分。离散化之后张三和王五都是第一名李四变成第二名。你看分数从97变成了1从88变成了2但“张三比李四分数高”这个事实一点没变。这就是离散化要做的事情。1.3 什么时候该用离散化判断一道题要不要离散化我一般看三个条件建议直接记下来数据范围很大大到开数组存不下比如坐标范围1e9实际用到的点数很少远远小于范围比如只有1e5个点题目只关心相对大小或相对位置不关心具体数值本身参与算术运算。三条同时满足基本就能确定需要离散化。反过来如果坐标范围在1e6以内那直接开数组反而更快更省事没必要多此一举。竞赛里不是所有大范围都要离散化int范围内直接存也行的情况也有——关键看你要不要用数组下标去索引这些值。2. C实现离散化的标准三件套2.1 sort unique lower_boundC里实现离散化有一套非常标准的流程我在比赛里写了无数次基本就是sort、unique、lower_bound三个函数配合。先说思路再给代码。假设我们有一堆需要离散化的原始数值存放在vectorint v里。第一步拷贝一份出来排序。第二步用unique去重——注意unique不是真的把重复元素删掉而是把不重复的元素挪到前面返回新的逻辑末尾迭代器。第三步对每个原始值用lower_bound在去重后的数组里找到它的位置这个位置的下标就是离散化后的编号。为什么一定要去重因为离散化之后我们通常要用编号作为数组下标同一个数值必须对应同一个下标否则后续统计就乱了。另外去重还能让离散化后的编号连续且紧凑最大编号就是不同数值的数量开数组的空间也能精确控制。#include bits/stdc.h using namespace std; vectorint discrete(vectorint a) { vectorint sorted a; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int x : a) { x lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin(); } return a; }这段代码返回的结果里原始值x被替换成了它在sorted中的排名从0开始。如果你希望编号从1开始lower_bound的结果后面加个1就行这在后面配合树状数组时经常用到因为树状数组的下标习惯从1开始0号位置通常空着。2.2 编号从0开始还是从1开始这是一个很容易忽略但影响很大的细节。我个人的习惯是如果离散化之后配合树状数组编号从1开始。因为树状数组的add和sum函数里idx lowbit(idx)这种操作从0开始会死循环而且大家约定俗成0号位不用。所以映射结果直接lower_bound(...) - begin 1。如果离散化之后配合线段树从0开始从1开始都可以看你线段树的写法。我自己写线段树习惯下标1为根所以也倾向于从1开始映射。如果只是做差值统计、前缀和、差分这类操作从0开始更自然因为后续的i - 1、i 1操作不需要反复调整边界。建议你在平时的模板里就统一好习惯不要每次都临时想。我自己的模板里写了一个带startIdx参数的版本默认从1开始需要从0开始的时候传个0就行这样比赛时不用纠结。2.3 手写二分 vs 直接用lower_bound很多人问过我lower_bound内部就是二分手写一个二分会不会更快我的答案是竞赛里直接lower_bound就够了不要自己手写。原因有两个。第一std::lower_bound是经过充分优化的大多数评测环境下它的常量和手写二分差距可以忽略不计。第二手写二分非常容易出边界错误——mid的取值、l和r的更新、循环终止条件任何一个细节写错结果就是离散化编号错位而且这种错位往往在样例数据上测不出来到了大数据才爆炸排查起来极其痛苦。我自己早期就吃过这个亏手写二分把l mid 1写成了l mid结果查找永远落在偏小的编号上一道扫描线的题调了一晚上。当然如果一场比赛里你需要处理多组离散化数据或者追求极致性能可以一次性把所有可能用到的值全部收集起来排序去重后用unordered_map建立映射这样查询就从O(log n)降到了O(1)。但这种做法在CSP-S里我一般不建议优先考虑因为unordered_map的常数其实不小而且如果题目本身对时间限制比较紧O(n log n)的离散化在整个算法里往往不是瓶颈。3. 实战场景一区间问题的离散化套路3.1 经典模型区间覆盖统计离散化最经典的用武之地是区间覆盖类问题。给你一堆区间[l, r]每个区间会“覆盖”一段范围最后问你某些点被多少个区间覆盖或者所有区间的总覆盖长度。这种题在CSP-S里非常常见近年的压轴题里经常作为其中一个环节出现。先说最朴素的思路如果坐标范围小直接用差分数组。diff[l]diff[r 1]--然后前缀和还原。但坐标范围一旦到了1e9差分数组直接开不下。这时候离散化就派上用场了——把区间端点收集起来离散化成紧凑的编号然后用一个长度不超过2n的数组来模拟差分。这里有一个关键细节区间端点离散化之后原本相邻的两个整数之间可能夹着没有被离散化的“空隙”。比如区间[1, 10]和[20, 30]离散化之后端点变成1, 10, 20, 30四个编号但如果你只是简单地对编号做差分中间的11到19这一段其实没有被任何区间覆盖却可能因为差分数组的连续性被错误地算成“覆盖了”。这就是区间离散化最容易踩的坑。解决办法有两种。第一种是把区间端点离散化之后额外在相邻离散点之间插入一个代表“空隙长度”的虚拟点差分时把空隙的长度也统计进去。第二种更常用记住一个原则对区间做覆盖统计时离散化单位不是“点”而是“段”。把相邻离散点之间的区间都看成一个独立的段每个段有一个长度这样差分和前缀和操作都作用在“段”上覆盖长度统计就准确了。3.2 完整代码配合差分的离散化写法我直接给出一个我在比赛中常用的模板解决“给定n个区间求被覆盖次数最多的点/段”这类问题。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint l(n), r(n); vectorint coords; for (int i 0; i n; i) { cin l[i] r[i]; coords.push_back(l[i]); coords.push_back(r[i]); // 如果统计的是覆盖长度且闭区间需要存 r[i] 1 coords.push_back(r[i] 1); } sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); int m coords.size(); vectorint diff(m 1, 0); for (int i 0; i n; i) { int idl lower_bound(coords.begin(), coords.end(), l[i]) - coords.begin(); int idr lower_bound(coords.begin(), coords.end(), r[i] 1) - coords.begin(); diff[idl]; diff[idr]--; } int maxCover 0, cur 0; for (int i 0; i m - 1; i) { cur diff[i]; int len coords[i 1] - coords[i]; maxCover max(maxCover, cur); // 这里是统计最大覆盖值 // 如果想算总覆盖长度就维护 cur 0 时的 len 之和 } cout maxCover endl; return 0; }注意这里我把r[i] 1也存进了coords。这招很关键如果题目给的区间是闭区间[l, r]那么“覆盖”到r为止r 1才算“不覆盖”。把r 1也加入离散化坐标系才能保证差分在r处正确结束。这是我的经验里最容易被忽略的细节很多人只存l和r结果边界永远差1。3.3 扫描线里的离散化为什么必须离散化扫描线是计算几何里的高频考点CSP-S偶尔会考而扫描线的实现几乎绕不开离散化。扫描线的核心思想是“用线段树维护当前扫描线覆盖的长度”其中线段树的下标范围来自所有矩形的左右边界纵坐标。如果不离散化线段树要开1e9的范围直接不可行。用离散化解决扫描线问题时线段树每个叶子节点代表的不是一个点而是一段区间。具体来说我们把所有矩形的上下边界纵坐标收集起来排序去重后得到y[0], y[1], ..., y[m-1]然后线段树的每个节点[l, r]代表纵坐标区间[y[l], y[r1]]。这是扫描线离散化最容易搞错的地方——线段树维护的不是“点坐标”而是“段坐标”节点数量和区间长度都要按m-1来计算。我见过太多人在这一步出错直接把纵坐标离散化后当作点来建树导致面积计算始终差一口气。记住一个口诀扫描线里离散化之后线段树的下标是“段”的编号不是“点”的编号。多体会一下这句话扫描线的坑能少踩一半。4. 实战场景二二维平面与离线查询4.1 二维离散化矩阵面积压缩除了区间和扫描线二维平面上的离散化也是CSP-S的常客。典型场景是平面上有若干个矩形或者点坐标范围很大但数量很少需要统计覆盖面积或者点的分布。二维离散化的思路和一位数本质相同但实现上要更小心。二维离散化的标准做法是把所有x坐标收集起来排序去重所有y坐标也收集起来排序去重然后两两组合成网格。关键在于二维离散化之后相邻格子之间同样存在空隙和一位区间离散化一样如果你只对离散化后的网格做处理空隙部分会被错误地忽略。我比较推荐的做法是把x坐标和y坐标分别离散化但额外记录相邻离散坐标之间的真实距离然后对压缩后的网格做二维差分。这样虽然代码量会大一些但胜在逻辑清晰不容易在边界条件上翻车。二维差分的模板一般配合diff[x1][y1]、diff[x2 1][y1]--、diff[x1][y2 1]--、diff[x2 1][y2 1]的形式实现离散化之后x2 1、y2 1这些索引要特别注意是否越界我的习惯是在坐标数组末尾多插入一个“无穷大”哨兵值避免边界判断的麻烦。4.2 离线查询为什么要先离散化有一类问题叫“离线查询”典型特征是给你一个数组然后有一大堆询问每个询问是“区间[l, r]内有多少个不同的数字”或者“区间内小于k的值有多少”。这类题在CSP-S里很常考而离散化在里面的作用是把原数组的数值压缩成紧凑的排名方便用树状数组或者线段树维护。我知道有些同学会想“那我直接用map存不就行了”这里我必须泼一盆冷水。map是基于红黑树实现的单次操作O(log n)看起来和离散化后的树状数组复杂度一样但常数差距巨大。而且离线查询往往有n和q都是1e5甚至更大的规模map的节点分配、内存跳转、缓存不命中都会让程序跑得很慢。我之前在学校OJ上测过同一道区间不同数字个数的题离散化 树状数组能跑进500ms而map版本直接2.5s起跳某些数据强的OJ直接超时。所以我的建议是在竞赛里能离散化就离散化不要把map当作替代方案。map可以用于调试、对拍、验证小数据但提交版本一定要用离散化。4.3 一个完整案例区间不同数字个数这里给出一个完整的离线处理 离散化案例让大家感受一下组合使用的感觉。这题是经典题做法是“离线右端点排序 树状数组”核心步骤包含离散化。#include bits/stdc.h using namespace std; const int MAXN 300005; int a[MAXN], ans[MAXN], last[MAXN]; int n, q; struct Query { int l, r, id; } queries[MAXN]; int main() { cin n; vectorint coords; for (int i 1; i n; i) { cin a[i]; coords.push_back(a[i]); } sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); for (int i 1; i n; i) { a[i] lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin() 1; } cin q; for (int i 0; i q; i) { cin queries[i].l queries[i].r; queries[i].id i; } sort(queries, queries q, [](const Query x, const Query y) { return x.r y.r; }); vectorint bit(n 2, 0); auto add [](int idx, int val) { while (idx n) { bit[idx] val; idx idx (-idx); } }; auto sum [](int idx) { int res 0; while (idx 0) { res bit[idx]; idx - idx (-idx); } return res; }; int curR 0; for (int i 0; i q; i) { while (curR queries[i].r) { curR; if (last[a[curR]]) { add(last[a[curR]], -1); } add(curR, 1); last[a[curR]] curR; } ans[queries[i].id] sum(queries[i].r) - sum(queries[i].l - 1); } for (int i 0; i q; i) { cout ans[i] endl; } return 0; }这段代码把离散化和树状数组组合在一起a[i]先被离散化成从1开始的编号然后树状数组记录“每个数字最后一次出现的位置”。排序查询后按右端点推进每次遇到重复数字就把之前的位置从树状数组里去掉再在当前新位置加上。这样每个查询区间内树状数组统计的就是“每个数字在当前区间内最后出现的位置数量”也就是不同数字的个数。这个案例非常有代表性建议大家亲手敲一遍把每一行的意图搞清楚。离散化 离线排序 树状数组这个组合在CSP-S里出现的频率非常高值得反复练习。5. 高频坑点与实战排查记录5.1 unique之后忘了erase这大概是初学者最常犯的错误。std::unique的机制是把不重复的元素移到数组前部然后返回“新逻辑末尾”的迭代器但它不会真正删除尾部剩余的元素。如果你忘了调用erase直接对unique返回的迭代器之后的区域进行lower_bound会因为数组里残留旧值而得到错误结果。我见过的最离谱的错误版本是sort之后只调用了unique没erase然后直接对原始数组lower_bound。这种代码在小数据上经常能“侥幸”通过因为残留的多余元素恰好排在被查询值之后lower_bound依然能命中正确位置。但一旦重复值多了残留元素的位置变化错误就出来了。所以写完离散化马上检查三行sort、unique、erase一个都不能少。5.2 lower_bound返回值可能等于end()另一个高频 bug 是查询值比离散化数组里所有值都大lower_bound返回end()减去begin()后得到的是sorted.size()也就是离散化数组长度而不是一个合法的编号。如果用这个去索引数组轻则越界读重则直接 RE。为什么会出现这种情况因为有些人写离散化时只收集了部分可能出现的值比如只收集了左端点而忘了右端点或者只收集了查询区间而忘了修改区间的端点。解决办法很简单在把所有需要用到的数值收集完之前不要急着排序去重。我写代码时的习惯是先把所有l、r、r1、查询的k等各种值全部push_back进coords检查一遍没有遗漏再统一排序去重。5.3 离散化后线段树的空间要开多少这是进阶选手也容易犯的错。假设有n个区间每个区间贡献两个端点算上r1之类的额外点离散化后一共m个坐标。大多数人的习惯是线段树开4 * m的数组这个量级基本够用。但如果你和我一样用“段”来建树实际需要的叶子节点数量是m - 1而内部节点总数不会超过4 * (m - 1)所以仍然开4 * m是安全的。但我真正想提醒的坑是有些题目故意让你在离散化之后做多个维度的处理比如既按 x 离散化建线段树又按 y 离散化建树状数组这时你很可能把两个数组的开销搞混。我的建议是给每一类数据结构单独定义一个MAXM常量至少是“对应维度坐标数量的 4 倍”并且再额外加5的余量。比赛时宁可多开一点内存也不要因为少开几个 int 而 RE这属于最不值得丢的分数。5.4 map能不能替代手写离散化这个问题我在前文提过这里再总结一下。map能替代的场景是你只需要做“点查询”不需要连续区间操作且数据量很小1e4以内。但CSP-S的大题里离散化之后往往接线段树、树状数组、扫描线、离线查询这类需要连续下标操作的数据结构这时候map就完全没法用了。另外map无法处理的一个场景是“区间更新、区间查询”。离散化之后你用线段树维护的是连续区间一个节点直接管辖[l, r]这一段而map的键值对是离散的点无法高效表达区间整体操作。所以别在这上面浪费时间去想替代方案了。在我个人带队的经验里离散化是那种“看起来简单、但细节极多”的知识点。它不像线段树那样复杂到让你望而却步但正因为简单很多人反而轻视它结果在赛场上因为边界问题白丢几十分。建议你把这篇文章里的模板整理进自己的板子里把坑点背下来然后专门刷几道配套练习巩固手感。最后再分享一个我自己的小习惯每道题写完离散化代码我都会立刻构造一组带重复值、带极值比如int最大值、最小值、带空区间的数据来测一遍。这三类边界数据能在三十秒内暴露九成以上的离散化错误比你事后debug一晚上划算得多。这个习惯帮我省了太多时间希望它也能帮到你。