你有没有遇到过这种情况一道题思路全靠模拟算法本身也不难结果一到代码实现就卡住了——不是逻辑想不明白而是题目给的数据范围实在太离谱数组根本开不出来。我最早接触离散化是在做竞赛题时遇到一个经典场景一张长度达到 1e9 的数轴上面零零散散放了不超过 1e5 个点让我统计这些点覆盖的区间长度。当时第一反应是开个布尔数组打标记结果一算内存直接放弃了。后来才知道这种“值域巨大但数量稀少”的问题正是离散化发挥威力的地方。离散化Discretization在算法里并不是一个独立的高级算法而是一种非常实用的预处理思想它把“数值很大、但实际出现的数值个数不多”的一组数据映射成一段连续的、紧凑的整数下标从而让原本开不下的数组变得可控让原本复杂度爆炸的遍历变得高效。这篇文章我会从原理讲到实现再结合典型例题和踩坑经历把离散化这个工具彻底聊透。不管你是准备信奥、考研刷题还是在日常开发里处理区间统计、数据映射这篇内容都应该对你有帮助。1. 离散化到底在解决什么问题1.1 先说一个反直觉的现象很多初学者听到“离散化”这个名字会觉得很高深其实它解决的核心问题特别朴素数据个数很少但数据取值范围极大。举个例子。假设现在有 1e5 个随机整数每个数的范围在 [0, 1e9] 之间。我想统计每个数出现的次数。最笨的办法是开一个长度为 1e91 的计数数组可这显然不现实——光初始化数组就能让程序直接内存超限。但如果把这些数从小到大排序再去重得到的可能只有 8e4 个互不相同的数。那么我完全可以把这 8e4 个数映射成 0 到 79999 的下标然后用一个长度 8e4 的数组去计数问题瞬间就解了。这就是离散化的本质保留数据之间的相对大小关系忽略它们实际数值之间的绝对差距。离散化之后原来需要 1e9 空间的存储需求被压缩到了 1e5 级别而数据之间“谁比谁大”这个信息完全没丢。1.2 离散化与哈希的区别很多人会问那用哈希表unordered_map不也能把大数值映射成小下标吗区别在哪这是一个特别关键的问题。哈希的核心特点是无序映射——它只负责把键对应到值但不保证键之间的顺序关系。而离散化的核心特点是保序映射——离散化之后下标的大小关系必须和原数值的大小关系完全一致。这个“保序”特性决定了离散化能配合二分查找、前缀和、树状数组、线段树这类依赖顺序的算法使用。比如你想在离散化后的数组上做二分查找原数值或者用树状数组统计某个排名区间内的数量这时候哈希就无能为力了只有离散化能做到。1.3 什么时候必须用离散化我总结了几类典型的“离散化刚需场景”供你对照判断值域巨大的统计类问题比如统计 1e9 范围内的区间覆盖长度、点的出现次数。典型如差分数组配合离散化把“对区间做加减”变成“对离散点做差分”。二维/三维坐标压缩平面直角坐标系上给你 1e5 个点坐标范围 1e9需要做矩阵覆盖统计。这时候横纵坐标分别离散化就能把稀疏的大坐标平面压缩成紧凑的网格。配合树状数组/线段树比如求逆序对、求区间不同数的个数这类问题需要“以值为下标”建树可值域一大就建不了离散化是标准解法。离线处理动态问题先把所有操作涉及到的值收集起来做离散化再把操作逐一应用。这类“离线离散化”的组合在竞赛题里极其常见。2. 最标准的离散化实现三步法拆解2.1 第一步收集所有可能出现的数值离散化最关键的前提是你必须在正式处理之前知道所有可能出现的数值。这决定了离散化通常是“离线”操作——先完整读入所有数据再统一处理。比如要离散化一个数组a {5, 2, 9, 2, 7, 5, 3}那么第一步就是把所有元素收集起来。如果是区间覆盖问题那么不仅要把区间的端点收集起来还要考虑是否把端点相邻的位置也收进来这点后面进阶部分会细说。这一步听起来简单但实际写代码时非常容易漏。比如有的题目会先给你一些插入操作再给你查询操作如果你在读入阶段不把所有涉及到的数值都存到一个备选数组里等真正处理到查询时才发现某个值没离散化那就晚了。所以务必要养成“先收集、后处理”的流程意识。2.2 第二步排序并去重收集完所有数值后把它们放进一个 vector或者其他动态数组接下来做两件事排序和去重。为什么要排序因为离散化后的下标必须体现原数值的大小关系而排序是让数组元素从小到大排列的最直接方式。排序之后“第几个元素”这个序号就天然反映了元素的大小排名。为什么要去重因为同一个数值可能多次出现如果不去重lower_bound返回的将是第一个匹配位置后面的重复元素也会占据不同下标导致“一个数值对应多个下标”映射关系就不是一一对应了。去重后的数组每个下标恰好对应一个唯一的原数值。在 C 里这两件事可以写得非常简洁vectorint all; // 假设已经把需要离散化的数值 push_back 进 all sort(all.begin(), all.end()); // 排序 all.erase(unique(all.begin(), all.end()), all.end()); // 去重这里有个小细节值得注意unique函数并不是真正把重复元素“删除”而是把不重复的元素移动到前面返回新逻辑末尾的迭代器。所以必须配合erase把尾部残余的重复元素真正清掉。很多刚接触的人只写了unique忘写erase结果数组长度没变后续二分查找的下标就全乱了。2.3 第三步二分查找建立映射排序去重完成后all数组就成了一个严格递增的“字典”每个下标 i 对应着一个唯一的原数值all[i]。接下来要把原始数据里的每个数替换成它的新下标。实现方法是用二分查找对每个原数值 x在all数组中找到第一个不小于 x 的位置这个位置的下标就是 x 离散化后的编号。在 C 中// 把 x 离散化为从 0 开始的下标 int id lower_bound(all.begin(), all.end(), x) - all.begin();由于 x 必然在all中存在前提是第一步收集时覆盖到了所有可能的 x所以lower_bound一定找得到不会返回end()。这里再补充一个习惯问题从 0 开始编号还是从 1 开始编号两种各有使用场景。从 0 开始编号写二分时最自然不需要额外偏移从 1 开始编号在配合树状数组、线段树时更顺手因为这类数据结构通常要求下标从 1 开始。我个人的习惯是收集时统一从 1 开始映射也就是int id lower_bound(all.begin(), all.end(), x) - all.begin() 1;这样后续写树状数组、线段树时无需频繁做下标偏移能省掉不少边界 bug。2.4 完整模板代码下面给一个我在竞赛和工程中都经常用的离散化模板以 1 为起始下标#include bits/stdc.h using namespace std; vectorint all; // 全局备选数组用于收集所有可能出现的数值 // 离散化主流程 void discretize(vectorint nums) { all nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int x : nums) { x lower_bound(all.begin(), all.end(), x) - all.begin() 1; } // 此时 nums 中每个数都变成了 1 到 all.size() 之间的编号 } int main() { vectorint a {5, 2, 9, 2, 7, 5, 3}; discretize(a); for (int x : a) cout x ; // 输出: 3 1 4 1 5 3 2 return 0; }注意看输出结果原数组{5, 2, 9, 2, 7, 5, 3}被映射成了{3, 1, 4, 1, 5, 3, 2}。原数值 2 是最小的对应编号 1原数值 9 是最大的对应编号 5。相对大小关系完全保留而数值范围从 [2, 9] 压缩到了 [1, 5]。这就是离散化的直观效果。2.5 复杂度分析离散化的时间复杂度主要来自排序为 O(n log n)其中 n 是收集到的数值总数。去重是 O(n)每个数的二分查找是 O(log n)所以总复杂度依然是 O(n log n)。这个开销在绝大多数场景下都是可以接受的即使面对 1e6 级别的数据量排序也只需不到一秒钟。空间复杂度是 O(n)主要用于存储备选数组。相比直接按值域开数组的 O(V)V 是值域大小当 V 远大于 n 时离散化的空间优势是压倒性的。3. 排序与二分离散化的左右护法3.1 为什么排序是第一块基石离散化的整个流程里排序起着决定性作用。如果没有排序我们收集到的数值是杂乱的根本无法建立“下标代表大小顺序”的映射关系。可以说离散化就是建立在有序数组之上的坐标重映射。一个很有意思的点是离散化经常和排序算法一起出现在综合题里。比如一个经典题目给定若干区间问这些区间总共覆盖了多少个不同的整数点。这时候需要把区间端点排序、去重、离散化然后再用差分数组处理覆盖次数。整个过程里你会用到快排sort、二分lower_bound、差分、前缀和——相当于把好几个基础算法串成了一条流水线。所以我一直觉得离散化是检验一个人对基础算法掌握程度的好题目。3.2 二分查找的边界到底该怎么选使用lower_bound还是upper_bound是离散化最容易出错的地方之一。我见过大量初学者在这里迷迷糊糊返回值差 1 就导致整个结果错误。核心原则是离散化查的是“这个数在有序数组中的准确排名”所以一定要用lower_bound找第一个不小于目标值的位置。upper_bound找的是第一个大于目标值的位置当数组中存在重复元素时两者行为有差异。不过我们在去重之后数组中每个数只出现一次所以理论上用lower_bound和upper_bound结果是一样的。但为了代码语义清晰建议统一使用lower_bound。另外还有一个小坑如果查询的值不在all数组中所谓“离散化不完全”lower_bound会返回一个“介于两者之间”的位置这个位置对应的下标是毫无意义的会直接导致逻辑错误。所以务必确认第一步收集阶段已经覆盖了所有查询值。3.3 从 0 开始还是从 1 开始一次说清楚这个问题我在不同群里被问过无数次这里给你一个可以直接抄的答案如果你只做普通映射、只求下标、不需要用树状数组或线段树从 0 开始更简洁如果你后续要接树状数组、线段树、差分数组这类“下标从 1 开始更安全”的结构从 1 开始。为什么树状数组特别在意下标从 1 开始因为树状数组的下标 0 是一个逻辑上的“死区”——对下标 0 执行add(0, val)会陷入死循环因为i lowbit(i)永远不会推进。如果你离散化后从 0 开始编号然后直接当树状数组下标用第一次 update 就可能出问题。所以我的模板统一从 1 开始最大程度规避这类坑。4. 一道典型例题从暴力到离散化的完整思路4.1 题目背景与考点题面给定一个长度为 n 的数列 a以及 m 次询问每次询问给出一个数值 x要求统计数列中小于等于 x 的元素个数。其中 n, m ≤ 1e5a 中元素和询问的 x 取值都在 [0, 1e9] 范围内。这道题如果在值域小的时候直接用计数数组 前缀和秒杀。但值域达到 1e9 时计数数组开不起来这时就需要离散化。思路是把 a 数组的所有元素和所有询问的 x 一并收进备选数组离散化之后用树状数组维护每个“数值编号”的出现次数再对每个询问在离散化后的编号上做前缀和查询。时间复杂度 O((nm) log(nm))完全可过。4.2 暴力做法的致命瓶颈先想想暴力怎么做最直接的办法是对于每个询问遍历整个数组统计满足条件的元素个数。这样做复杂度是 O(nm)在 n 和 m 都等于 1e5 时总操作次数高达 1e10任何语言都跑不动。如果值域只有 1e6我们可以开一个长度为 1e6 的计数数组统计每个值出现的次数再做前缀和每个询问 O(1) 回答。这是“值域可行”时的最优解。可一旦值域变成 1e9数组根本开不出来——这就是离散化登场的时候。离散化的意义在于我们并不关心数值到底是 123456789 还是 987654321我们只关心它们之间的大小排名所以可以把 1e9 的范围压缩到最多 nm 个编号。4.3 离散化题解代码#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN * 2]; // 树状数组注意大小要开到 n m 级别 int n, m; vectorint all; vectorint a, query; int lowbit(int x) { return x (-x); } void add(int idx, int val) { while (idx all.size()) { tree[idx] val; idx lowbit(idx); } } int prefixSum(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; a.resize(n); query.resize(m); for (int i 0; i n; i) { cin a[i]; all.push_back(a[i]); } for (int i 0; i m; i) { cin query[i]; all.push_back(query[i]); } // 离散化排序 去重 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 插入 a 中的元素下标从 1 开始 for (int i 0; i n; i) { int id lower_bound(all.begin(), all.end(), a[i]) - all.begin() 1; add(id, 1); } // 回答询问 for (int i 0; i m; i) { int id lower_bound(all.begin(), all.end(), query[i]) - all.begin() 1; cout prefixSum(id) \n; } return 0; }这段代码的关键点在于查询的 x 也提前放进了备选数组。这一步极其重要否则lower_bound查不到 x 的准确编号整个程序就会得到错误结果。如果你希望查询某个 x 的“小于等于它的元素个数”而 x 没在 all 里前缀和查询就没有意义了。4.4 这道题对树状数组初学者的额外价值很多初学者一开始接触树状数组时总觉得它只用来处理“求前缀和”“区间更新”这类模板题不知道值域大时该拿它怎么办。这道题正好把“树状数组”和“离散化”两个知识点结合起来树状数组按下标维护信息下标需要紧凑、连续离散化正是制造这种紧凑下标的工具。两者天然互补。我在带团队面试时也经常用这道题来考察候选人的基础功底。能独立把离散化和树状数组串起来的人通常说明他对“数据结构处理的是下标而不是值”这件事理解得比较到位。5. 我踩过的那些坑离散化的边界与细节5.1 忘了把查询值也收进备选数组这是离散化最经典的坑我早期做区间查询类题目时吃过好几次亏。比如你离散化了一个数组 a然后想对某个不在 a 中出现的数值 x 做查找lower_bound确实也能返回一个位置这个位置对应的是“第一个不小于 x 的元素”的编号。如果你只是想统计“小于等于 x 的元素数量”这个位置似乎也可以用——但前提是你理解这里的语义差异。问题是当你需要精确统计时这种“插入到相邻位置之间”的编号是没有被树状数组初始化过的prefixSum 得到的结果边界语义就可能出错。所以最稳妥的解决方案永远是凡是查询会涉及到的数值都提前收集进 all 数组不做任何“现场再处理”的幻想。5.2 忘记 unique 之后要 eraseunique并不会真正缩减数组大小只是把不重复元素移到前面。如果你忘了 erase后面all.size()会比实际不重复元素数大这会导致树状数组的容量判断错误还可能让二分查找结果偏移。更隐蔽的是有些编译器环境下lower_bound对于去重不完全的数组依然能返回正确结果这反而会掩盖问题让你在不知不觉中埋下 bug。所以我的建议是写完排序去重后立刻检查 all.size() 是否符合预期。5.3 二维离散化中的“格子”与“点”这是进阶内容里最容易翻车的点。在二维平面问题中如果我们要统计矩形区域的覆盖面积离散化之后横纵坐标会形成若干“格子”而不是“点”。一个具体坐标离散化后对应的是“某个边界位置”而不是“某个格子编号”。举个例子一条线段从 x1 覆盖到 x3如果只把 {1, 3} 离散化那么两个边界之间长度为 3-12 的区间被压缩成了一个格子。但如果你把 {1, 2, 3} 都离散化就能区分出 [1,2] 和 [2,3] 两个格子覆盖长度就会按格子累加。在“点覆盖”问题里用前者没问题在“区间长度覆盖”问题里必须把所有端点端点之间的值都收集进去否则就会丢失实际距离信息。所以二维离散化并不是简单地调用两次一维离散化而是要提前想清楚你关心的是“点”还是“区间”这决定了你要不要把相邻坐标的中间值也收进备选数组。这个坑在扫描线求矩形面积并时尤其常见值得专门注意。5.4 离散化之后还能不能做加法这是个很多人忽略的“语义”问题。离散化后数组下标之间的“距离”由 1 个 index 组成但这并不代表原数值之差也是 1。举个例子数值 100 和 200 离散化后可能是编号 1 和 2但它们的真实差值明明是 100。所以如果你需要利用数值之间的真实间距做计算比如求覆盖区间的实际长度离散化之后不能直接用下标差替代。解决办法是保留原始的 all 数组它记录着每个编号对应的真实值需要计算真实间距时用all[r] - all[l]来还原。这种“下标-真实值”的一一映射关系既是离散化的优势也是使用时必须时刻记住的边界。5.5 空间估算失误离散化虽然解决了值域大的问题但空间复杂度并不是“数值个数”而是“所有出现在场景中的值的个数”。如果题目里既有 m 次修改、m 次查询且修改会引入新值那么收集到的值最多可能是 2m 个甚至更多。有些人在数组开大小时只按 n 算结果需要存 2n 个值时就爆了。稳妥做法是先用 vector 收集最后按 all.size() 动态申请树状数组大小不要拍脑袋写固定数组大小。6. 进阶方向二维离散化与扫描线6.1 从一维到二维坐标压缩的思路当问题上升到二维比如给你 1e5 个矩形求它们的覆盖面积总和直接用二维差分数组是不现实的——坐标范围可能达到 1e9。这时就需要对 x 坐标和 y 坐标分别做离散化。核心思路是把所有矩形的左右边界 x 值、上下边界 y 值收集起来分别排序去重。假设 x 方向得到 X 个不同坐标y 方向得到 Y 个不同坐标那么整个平面就被压缩成了一个 X×Y 的网格。每个矩形的覆盖范围在离散化坐标里对应了一个矩形区域。传统做法是在这个压缩网格上做二维差分或直接标记覆盖然后扫描一遍网格累加被覆盖格子的真实面积。真实面积怎么算不能用网格的行列数直接乘而要用(x_idx[i1] - x_idx[i]) * (y_idx[j1] - y_idx[j])来计算每个格子的实际面积。这就是 5.4 节提到的“离散化后不能直接拿下标做距离”在二维场景的典型体现。6.2 扫描线法与离散化的经典配合扫描线是计算矩形覆盖面积、周长问题的常用算法它天然依赖离散化。基本流程是按 y 坐标排序的所有水平边矩形的上边和下边自下而上扫描每条边对应一个 x 区间扫描到矩形的下边时把该 x 区间覆盖次数加一扫到上边时减一。当前“被覆盖的 x 区间总长度”乘以当前边与下一条边的 y 坐标差就是这一段扫描区域的面积增量。这里的 x 区间覆盖次数需要用线段树来维护而线段树不可能直接建立在整个 x 取值范围上所以必须先对所有 x 坐标离散化。离散化后线段树的每个叶子节点代表的是一个“x 区间段”而不是一个“x 点”——这是扫描线实现里最容易让人困惑的点。你维护的“区间加一/减一”操作操作的其实是离散化后的区间编号。这也是为什么我说离散化是一把双刃剑它把范围压缩了但也改变了问题里“点”和“区间”的概念。用对了扫描线的代码行数不会太长用错了输出结果差个一两倍都不知道去哪排查。6.3 对工程场景的启发别以为离散化只能在竞赛题里见到。日常开发中凡是涉及“大 ID 映射成紧凑序号”的场景思路都是离散化。比如数据库里一个表有上亿行但某个字段的去重值只有几千个这时建立“值到编号”的字典可以显著压缩索引体积再比如日志分析中把 IP 地址映射成编号再做频次统计本质上也是离散化的应用。理解了离散化的原理你在设计数据映射层时就能自然地想到“先收集全量值再做排序去重和映射”这套方法论而不是简单粗暴地套一层哈希表。我在实际项目中处理过传感器上报数据的存储优化设备 id 是一个很长的字符串但活跃设备就几千台。我把所有出现过的设备 id 收集起来排序去重编号后存入内部数据结构存储空间直接降了一个数量级查询还因为编号有序可以走二分顺带提升了性能。这说明离散化不是纸上谈兵的算法而是能真正落地的工程技巧。7. 写在最后的一点经验离散化这个技术表面上看代码量很小就是“排序、去重、二分”三件套但真正吃透它需要理解和“值域”相关的若干细节。我见过太多人在排序去重上栽跟头也见过太多人在二维坐标压缩时忽略了“点”和“格子”的差别导致结果偏差。如果你打算系统掌握它我的建议是先把一维离散化模板练到闭着眼睛能写再找两三道区间覆盖、统计类题目巩固最后用扫描线题目检验自己对“区间段”的理解是否到位。另外做离散化类题目时强烈建议写之前先花一分钟想一想哪些数值会进入备选数组进入数组后一个数值编号是否唯一的、连续地从 1或 0排到 N后续操作是在“编号”上做还是需要还原真实数值把这三个问题想清楚你就能避开大部分常见的坑。我自己每次写离散化代码之前都会在心里默念一遍这三个问题这已经成了我的固定习惯也算是踩了几年坑之后沉淀下来的一点经验。
离散化算法详解：从原理到实践，压缩值域解决大范围数据问题
你有没有遇到过这种情况一道题思路全靠模拟算法本身也不难结果一到代码实现就卡住了——不是逻辑想不明白而是题目给的数据范围实在太离谱数组根本开不出来。我最早接触离散化是在做竞赛题时遇到一个经典场景一张长度达到 1e9 的数轴上面零零散散放了不超过 1e5 个点让我统计这些点覆盖的区间长度。当时第一反应是开个布尔数组打标记结果一算内存直接放弃了。后来才知道这种“值域巨大但数量稀少”的问题正是离散化发挥威力的地方。离散化Discretization在算法里并不是一个独立的高级算法而是一种非常实用的预处理思想它把“数值很大、但实际出现的数值个数不多”的一组数据映射成一段连续的、紧凑的整数下标从而让原本开不下的数组变得可控让原本复杂度爆炸的遍历变得高效。这篇文章我会从原理讲到实现再结合典型例题和踩坑经历把离散化这个工具彻底聊透。不管你是准备信奥、考研刷题还是在日常开发里处理区间统计、数据映射这篇内容都应该对你有帮助。1. 离散化到底在解决什么问题1.1 先说一个反直觉的现象很多初学者听到“离散化”这个名字会觉得很高深其实它解决的核心问题特别朴素数据个数很少但数据取值范围极大。举个例子。假设现在有 1e5 个随机整数每个数的范围在 [0, 1e9] 之间。我想统计每个数出现的次数。最笨的办法是开一个长度为 1e91 的计数数组可这显然不现实——光初始化数组就能让程序直接内存超限。但如果把这些数从小到大排序再去重得到的可能只有 8e4 个互不相同的数。那么我完全可以把这 8e4 个数映射成 0 到 79999 的下标然后用一个长度 8e4 的数组去计数问题瞬间就解了。这就是离散化的本质保留数据之间的相对大小关系忽略它们实际数值之间的绝对差距。离散化之后原来需要 1e9 空间的存储需求被压缩到了 1e5 级别而数据之间“谁比谁大”这个信息完全没丢。1.2 离散化与哈希的区别很多人会问那用哈希表unordered_map不也能把大数值映射成小下标吗区别在哪这是一个特别关键的问题。哈希的核心特点是无序映射——它只负责把键对应到值但不保证键之间的顺序关系。而离散化的核心特点是保序映射——离散化之后下标的大小关系必须和原数值的大小关系完全一致。这个“保序”特性决定了离散化能配合二分查找、前缀和、树状数组、线段树这类依赖顺序的算法使用。比如你想在离散化后的数组上做二分查找原数值或者用树状数组统计某个排名区间内的数量这时候哈希就无能为力了只有离散化能做到。1.3 什么时候必须用离散化我总结了几类典型的“离散化刚需场景”供你对照判断值域巨大的统计类问题比如统计 1e9 范围内的区间覆盖长度、点的出现次数。典型如差分数组配合离散化把“对区间做加减”变成“对离散点做差分”。二维/三维坐标压缩平面直角坐标系上给你 1e5 个点坐标范围 1e9需要做矩阵覆盖统计。这时候横纵坐标分别离散化就能把稀疏的大坐标平面压缩成紧凑的网格。配合树状数组/线段树比如求逆序对、求区间不同数的个数这类问题需要“以值为下标”建树可值域一大就建不了离散化是标准解法。离线处理动态问题先把所有操作涉及到的值收集起来做离散化再把操作逐一应用。这类“离线离散化”的组合在竞赛题里极其常见。2. 最标准的离散化实现三步法拆解2.1 第一步收集所有可能出现的数值离散化最关键的前提是你必须在正式处理之前知道所有可能出现的数值。这决定了离散化通常是“离线”操作——先完整读入所有数据再统一处理。比如要离散化一个数组a {5, 2, 9, 2, 7, 5, 3}那么第一步就是把所有元素收集起来。如果是区间覆盖问题那么不仅要把区间的端点收集起来还要考虑是否把端点相邻的位置也收进来这点后面进阶部分会细说。这一步听起来简单但实际写代码时非常容易漏。比如有的题目会先给你一些插入操作再给你查询操作如果你在读入阶段不把所有涉及到的数值都存到一个备选数组里等真正处理到查询时才发现某个值没离散化那就晚了。所以务必要养成“先收集、后处理”的流程意识。2.2 第二步排序并去重收集完所有数值后把它们放进一个 vector或者其他动态数组接下来做两件事排序和去重。为什么要排序因为离散化后的下标必须体现原数值的大小关系而排序是让数组元素从小到大排列的最直接方式。排序之后“第几个元素”这个序号就天然反映了元素的大小排名。为什么要去重因为同一个数值可能多次出现如果不去重lower_bound返回的将是第一个匹配位置后面的重复元素也会占据不同下标导致“一个数值对应多个下标”映射关系就不是一一对应了。去重后的数组每个下标恰好对应一个唯一的原数值。在 C 里这两件事可以写得非常简洁vectorint all; // 假设已经把需要离散化的数值 push_back 进 all sort(all.begin(), all.end()); // 排序 all.erase(unique(all.begin(), all.end()), all.end()); // 去重这里有个小细节值得注意unique函数并不是真正把重复元素“删除”而是把不重复的元素移动到前面返回新逻辑末尾的迭代器。所以必须配合erase把尾部残余的重复元素真正清掉。很多刚接触的人只写了unique忘写erase结果数组长度没变后续二分查找的下标就全乱了。2.3 第三步二分查找建立映射排序去重完成后all数组就成了一个严格递增的“字典”每个下标 i 对应着一个唯一的原数值all[i]。接下来要把原始数据里的每个数替换成它的新下标。实现方法是用二分查找对每个原数值 x在all数组中找到第一个不小于 x 的位置这个位置的下标就是 x 离散化后的编号。在 C 中// 把 x 离散化为从 0 开始的下标 int id lower_bound(all.begin(), all.end(), x) - all.begin();由于 x 必然在all中存在前提是第一步收集时覆盖到了所有可能的 x所以lower_bound一定找得到不会返回end()。这里再补充一个习惯问题从 0 开始编号还是从 1 开始编号两种各有使用场景。从 0 开始编号写二分时最自然不需要额外偏移从 1 开始编号在配合树状数组、线段树时更顺手因为这类数据结构通常要求下标从 1 开始。我个人的习惯是收集时统一从 1 开始映射也就是int id lower_bound(all.begin(), all.end(), x) - all.begin() 1;这样后续写树状数组、线段树时无需频繁做下标偏移能省掉不少边界 bug。2.4 完整模板代码下面给一个我在竞赛和工程中都经常用的离散化模板以 1 为起始下标#include bits/stdc.h using namespace std; vectorint all; // 全局备选数组用于收集所有可能出现的数值 // 离散化主流程 void discretize(vectorint nums) { all nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int x : nums) { x lower_bound(all.begin(), all.end(), x) - all.begin() 1; } // 此时 nums 中每个数都变成了 1 到 all.size() 之间的编号 } int main() { vectorint a {5, 2, 9, 2, 7, 5, 3}; discretize(a); for (int x : a) cout x ; // 输出: 3 1 4 1 5 3 2 return 0; }注意看输出结果原数组{5, 2, 9, 2, 7, 5, 3}被映射成了{3, 1, 4, 1, 5, 3, 2}。原数值 2 是最小的对应编号 1原数值 9 是最大的对应编号 5。相对大小关系完全保留而数值范围从 [2, 9] 压缩到了 [1, 5]。这就是离散化的直观效果。2.5 复杂度分析离散化的时间复杂度主要来自排序为 O(n log n)其中 n 是收集到的数值总数。去重是 O(n)每个数的二分查找是 O(log n)所以总复杂度依然是 O(n log n)。这个开销在绝大多数场景下都是可以接受的即使面对 1e6 级别的数据量排序也只需不到一秒钟。空间复杂度是 O(n)主要用于存储备选数组。相比直接按值域开数组的 O(V)V 是值域大小当 V 远大于 n 时离散化的空间优势是压倒性的。3. 排序与二分离散化的左右护法3.1 为什么排序是第一块基石离散化的整个流程里排序起着决定性作用。如果没有排序我们收集到的数值是杂乱的根本无法建立“下标代表大小顺序”的映射关系。可以说离散化就是建立在有序数组之上的坐标重映射。一个很有意思的点是离散化经常和排序算法一起出现在综合题里。比如一个经典题目给定若干区间问这些区间总共覆盖了多少个不同的整数点。这时候需要把区间端点排序、去重、离散化然后再用差分数组处理覆盖次数。整个过程里你会用到快排sort、二分lower_bound、差分、前缀和——相当于把好几个基础算法串成了一条流水线。所以我一直觉得离散化是检验一个人对基础算法掌握程度的好题目。3.2 二分查找的边界到底该怎么选使用lower_bound还是upper_bound是离散化最容易出错的地方之一。我见过大量初学者在这里迷迷糊糊返回值差 1 就导致整个结果错误。核心原则是离散化查的是“这个数在有序数组中的准确排名”所以一定要用lower_bound找第一个不小于目标值的位置。upper_bound找的是第一个大于目标值的位置当数组中存在重复元素时两者行为有差异。不过我们在去重之后数组中每个数只出现一次所以理论上用lower_bound和upper_bound结果是一样的。但为了代码语义清晰建议统一使用lower_bound。另外还有一个小坑如果查询的值不在all数组中所谓“离散化不完全”lower_bound会返回一个“介于两者之间”的位置这个位置对应的下标是毫无意义的会直接导致逻辑错误。所以务必确认第一步收集阶段已经覆盖了所有查询值。3.3 从 0 开始还是从 1 开始一次说清楚这个问题我在不同群里被问过无数次这里给你一个可以直接抄的答案如果你只做普通映射、只求下标、不需要用树状数组或线段树从 0 开始更简洁如果你后续要接树状数组、线段树、差分数组这类“下标从 1 开始更安全”的结构从 1 开始。为什么树状数组特别在意下标从 1 开始因为树状数组的下标 0 是一个逻辑上的“死区”——对下标 0 执行add(0, val)会陷入死循环因为i lowbit(i)永远不会推进。如果你离散化后从 0 开始编号然后直接当树状数组下标用第一次 update 就可能出问题。所以我的模板统一从 1 开始最大程度规避这类坑。4. 一道典型例题从暴力到离散化的完整思路4.1 题目背景与考点题面给定一个长度为 n 的数列 a以及 m 次询问每次询问给出一个数值 x要求统计数列中小于等于 x 的元素个数。其中 n, m ≤ 1e5a 中元素和询问的 x 取值都在 [0, 1e9] 范围内。这道题如果在值域小的时候直接用计数数组 前缀和秒杀。但值域达到 1e9 时计数数组开不起来这时就需要离散化。思路是把 a 数组的所有元素和所有询问的 x 一并收进备选数组离散化之后用树状数组维护每个“数值编号”的出现次数再对每个询问在离散化后的编号上做前缀和查询。时间复杂度 O((nm) log(nm))完全可过。4.2 暴力做法的致命瓶颈先想想暴力怎么做最直接的办法是对于每个询问遍历整个数组统计满足条件的元素个数。这样做复杂度是 O(nm)在 n 和 m 都等于 1e5 时总操作次数高达 1e10任何语言都跑不动。如果值域只有 1e6我们可以开一个长度为 1e6 的计数数组统计每个值出现的次数再做前缀和每个询问 O(1) 回答。这是“值域可行”时的最优解。可一旦值域变成 1e9数组根本开不出来——这就是离散化登场的时候。离散化的意义在于我们并不关心数值到底是 123456789 还是 987654321我们只关心它们之间的大小排名所以可以把 1e9 的范围压缩到最多 nm 个编号。4.3 离散化题解代码#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN * 2]; // 树状数组注意大小要开到 n m 级别 int n, m; vectorint all; vectorint a, query; int lowbit(int x) { return x (-x); } void add(int idx, int val) { while (idx all.size()) { tree[idx] val; idx lowbit(idx); } } int prefixSum(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; a.resize(n); query.resize(m); for (int i 0; i n; i) { cin a[i]; all.push_back(a[i]); } for (int i 0; i m; i) { cin query[i]; all.push_back(query[i]); } // 离散化排序 去重 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 插入 a 中的元素下标从 1 开始 for (int i 0; i n; i) { int id lower_bound(all.begin(), all.end(), a[i]) - all.begin() 1; add(id, 1); } // 回答询问 for (int i 0; i m; i) { int id lower_bound(all.begin(), all.end(), query[i]) - all.begin() 1; cout prefixSum(id) \n; } return 0; }这段代码的关键点在于查询的 x 也提前放进了备选数组。这一步极其重要否则lower_bound查不到 x 的准确编号整个程序就会得到错误结果。如果你希望查询某个 x 的“小于等于它的元素个数”而 x 没在 all 里前缀和查询就没有意义了。4.4 这道题对树状数组初学者的额外价值很多初学者一开始接触树状数组时总觉得它只用来处理“求前缀和”“区间更新”这类模板题不知道值域大时该拿它怎么办。这道题正好把“树状数组”和“离散化”两个知识点结合起来树状数组按下标维护信息下标需要紧凑、连续离散化正是制造这种紧凑下标的工具。两者天然互补。我在带团队面试时也经常用这道题来考察候选人的基础功底。能独立把离散化和树状数组串起来的人通常说明他对“数据结构处理的是下标而不是值”这件事理解得比较到位。5. 我踩过的那些坑离散化的边界与细节5.1 忘了把查询值也收进备选数组这是离散化最经典的坑我早期做区间查询类题目时吃过好几次亏。比如你离散化了一个数组 a然后想对某个不在 a 中出现的数值 x 做查找lower_bound确实也能返回一个位置这个位置对应的是“第一个不小于 x 的元素”的编号。如果你只是想统计“小于等于 x 的元素数量”这个位置似乎也可以用——但前提是你理解这里的语义差异。问题是当你需要精确统计时这种“插入到相邻位置之间”的编号是没有被树状数组初始化过的prefixSum 得到的结果边界语义就可能出错。所以最稳妥的解决方案永远是凡是查询会涉及到的数值都提前收集进 all 数组不做任何“现场再处理”的幻想。5.2 忘记 unique 之后要 eraseunique并不会真正缩减数组大小只是把不重复元素移到前面。如果你忘了 erase后面all.size()会比实际不重复元素数大这会导致树状数组的容量判断错误还可能让二分查找结果偏移。更隐蔽的是有些编译器环境下lower_bound对于去重不完全的数组依然能返回正确结果这反而会掩盖问题让你在不知不觉中埋下 bug。所以我的建议是写完排序去重后立刻检查 all.size() 是否符合预期。5.3 二维离散化中的“格子”与“点”这是进阶内容里最容易翻车的点。在二维平面问题中如果我们要统计矩形区域的覆盖面积离散化之后横纵坐标会形成若干“格子”而不是“点”。一个具体坐标离散化后对应的是“某个边界位置”而不是“某个格子编号”。举个例子一条线段从 x1 覆盖到 x3如果只把 {1, 3} 离散化那么两个边界之间长度为 3-12 的区间被压缩成了一个格子。但如果你把 {1, 2, 3} 都离散化就能区分出 [1,2] 和 [2,3] 两个格子覆盖长度就会按格子累加。在“点覆盖”问题里用前者没问题在“区间长度覆盖”问题里必须把所有端点端点之间的值都收集进去否则就会丢失实际距离信息。所以二维离散化并不是简单地调用两次一维离散化而是要提前想清楚你关心的是“点”还是“区间”这决定了你要不要把相邻坐标的中间值也收进备选数组。这个坑在扫描线求矩形面积并时尤其常见值得专门注意。5.4 离散化之后还能不能做加法这是个很多人忽略的“语义”问题。离散化后数组下标之间的“距离”由 1 个 index 组成但这并不代表原数值之差也是 1。举个例子数值 100 和 200 离散化后可能是编号 1 和 2但它们的真实差值明明是 100。所以如果你需要利用数值之间的真实间距做计算比如求覆盖区间的实际长度离散化之后不能直接用下标差替代。解决办法是保留原始的 all 数组它记录着每个编号对应的真实值需要计算真实间距时用all[r] - all[l]来还原。这种“下标-真实值”的一一映射关系既是离散化的优势也是使用时必须时刻记住的边界。5.5 空间估算失误离散化虽然解决了值域大的问题但空间复杂度并不是“数值个数”而是“所有出现在场景中的值的个数”。如果题目里既有 m 次修改、m 次查询且修改会引入新值那么收集到的值最多可能是 2m 个甚至更多。有些人在数组开大小时只按 n 算结果需要存 2n 个值时就爆了。稳妥做法是先用 vector 收集最后按 all.size() 动态申请树状数组大小不要拍脑袋写固定数组大小。6. 进阶方向二维离散化与扫描线6.1 从一维到二维坐标压缩的思路当问题上升到二维比如给你 1e5 个矩形求它们的覆盖面积总和直接用二维差分数组是不现实的——坐标范围可能达到 1e9。这时就需要对 x 坐标和 y 坐标分别做离散化。核心思路是把所有矩形的左右边界 x 值、上下边界 y 值收集起来分别排序去重。假设 x 方向得到 X 个不同坐标y 方向得到 Y 个不同坐标那么整个平面就被压缩成了一个 X×Y 的网格。每个矩形的覆盖范围在离散化坐标里对应了一个矩形区域。传统做法是在这个压缩网格上做二维差分或直接标记覆盖然后扫描一遍网格累加被覆盖格子的真实面积。真实面积怎么算不能用网格的行列数直接乘而要用(x_idx[i1] - x_idx[i]) * (y_idx[j1] - y_idx[j])来计算每个格子的实际面积。这就是 5.4 节提到的“离散化后不能直接拿下标做距离”在二维场景的典型体现。6.2 扫描线法与离散化的经典配合扫描线是计算矩形覆盖面积、周长问题的常用算法它天然依赖离散化。基本流程是按 y 坐标排序的所有水平边矩形的上边和下边自下而上扫描每条边对应一个 x 区间扫描到矩形的下边时把该 x 区间覆盖次数加一扫到上边时减一。当前“被覆盖的 x 区间总长度”乘以当前边与下一条边的 y 坐标差就是这一段扫描区域的面积增量。这里的 x 区间覆盖次数需要用线段树来维护而线段树不可能直接建立在整个 x 取值范围上所以必须先对所有 x 坐标离散化。离散化后线段树的每个叶子节点代表的是一个“x 区间段”而不是一个“x 点”——这是扫描线实现里最容易让人困惑的点。你维护的“区间加一/减一”操作操作的其实是离散化后的区间编号。这也是为什么我说离散化是一把双刃剑它把范围压缩了但也改变了问题里“点”和“区间”的概念。用对了扫描线的代码行数不会太长用错了输出结果差个一两倍都不知道去哪排查。6.3 对工程场景的启发别以为离散化只能在竞赛题里见到。日常开发中凡是涉及“大 ID 映射成紧凑序号”的场景思路都是离散化。比如数据库里一个表有上亿行但某个字段的去重值只有几千个这时建立“值到编号”的字典可以显著压缩索引体积再比如日志分析中把 IP 地址映射成编号再做频次统计本质上也是离散化的应用。理解了离散化的原理你在设计数据映射层时就能自然地想到“先收集全量值再做排序去重和映射”这套方法论而不是简单粗暴地套一层哈希表。我在实际项目中处理过传感器上报数据的存储优化设备 id 是一个很长的字符串但活跃设备就几千台。我把所有出现过的设备 id 收集起来排序去重编号后存入内部数据结构存储空间直接降了一个数量级查询还因为编号有序可以走二分顺带提升了性能。这说明离散化不是纸上谈兵的算法而是能真正落地的工程技巧。7. 写在最后的一点经验离散化这个技术表面上看代码量很小就是“排序、去重、二分”三件套但真正吃透它需要理解和“值域”相关的若干细节。我见过太多人在排序去重上栽跟头也见过太多人在二维坐标压缩时忽略了“点”和“格子”的差别导致结果偏差。如果你打算系统掌握它我的建议是先把一维离散化模板练到闭着眼睛能写再找两三道区间覆盖、统计类题目巩固最后用扫描线题目检验自己对“区间段”的理解是否到位。另外做离散化类题目时强烈建议写之前先花一分钟想一想哪些数值会进入备选数组进入数组后一个数值编号是否唯一的、连续地从 1或 0排到 N后续操作是在“编号”上做还是需要还原真实数值把这三个问题想清楚你就能避开大部分常见的坑。我自己每次写离散化代码之前都会在心里默念一遍这三个问题这已经成了我的固定习惯也算是踩了几年坑之后沉淀下来的一点经验。
