你有没有遇到过这种情况：一道题思路全靠模拟，算法本身也不难，结果一到代码实现就卡住了——不是逻辑想不明白，而是题目给的数据范围实在太离谱，数组根本开不出来。我最早接触离散化是在做竞赛题时遇到一个经典场景：一张长度达到 1e9 的数轴，上面零零散散放了不超过 1e5 个点，让我统计这些点覆盖的区间长度。当时第一反应是开个布尔数组打标记，结果一算内存，直接放弃了。后来才知道，这种“值域巨大但数量稀少”的问题，正是离散化发挥威力的地方。
离散化（Discretization）在算法里并不是一个独立的高级算法，而是一种非常实用的预处理思想：它把“数值很大、但实际出现的数值个数不多”的一组数据，映射成一段连续的、紧凑的整数下标，从而让原本开不下的数组变得可控，让原本复杂度爆炸的遍历变得高效。这篇文章我会从原理讲到实现，再结合典型例题和踩坑经历，把离散化这个工具彻底聊透。不管你是准备信奥、考研刷题，还是在日常开发里处理区间统计、数据映射，这篇内容都应该对你有帮助。
1. 离散化到底在解决什么问题
1.1 先说一个反直觉的现象
很多初学者听到“离散化”这个名字会觉得很高深，其实它解决的核心问题特别朴素：数据个数很少，但数据取值范围极大。
举个例子。假设现在有 1e5 个随机整数，每个数的范围在 [0, 1e9] 之间。我想统计每个数出现的次数。最笨的办法是开一个长度为 1e9+1 的计数数组，可这显然不现实——光初始化数组就能让程序直接内存超限。但如果把这些数从小到大排序再去重，得到的可能只有 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++ 里，这两件事可以写得非常简洁：
vector<int> 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; vector<int> all; // 全局备选数组，用于收集所有可能出现的数值 // 离散化主流程 void discretize(vector<int>& 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() { vector<int> 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 ≤ 1e5，a 中元素和询问的 x 取值都在 [0, 1e9] 范围内。
这道题如果在值域小的时候，直接用计数数组 + 前缀和秒杀。但值域达到 1e9 时，计数数组开不起来，这时就需要离散化。思路是：把 a 数组的所有元素和所有询问的 x 一并收进备选数组，离散化之后，用树状数组维护每个“数值编号”的出现次数，再对每个询问在离散化后的编号上做前缀和查询。时间复杂度 O((n+m) log(n+m))，完全可过。
4.2 暴力做法的致命瓶颈
先想想暴力怎么做：最直接的办法是对于每个询问，遍历整个数组统计满足条件的元素个数。这样做复杂度是 O(nm)，在 n 和 m 都等于 1e5 时，总操作次数高达 1e10，任何语言都跑不动。
如果值域只有 1e6，我们可以开一个长度为 1e6 的计数数组，统计每个值出现的次数，再做前缀和，每个询问 O(1) 回答。这是“值域可行”时的最优解。可一旦值域变成 1e9，数组根本开不出来——这就是离散化登场的时候。离散化的意义在于，我们并不关心数值到底是 123456789 还是 987654321，我们只关心它们之间的大小排名，所以可以把 1e9 的范围压缩到最多 n+m 个编号。
4.3 离散化题解代码
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int tree[MAXN * 2]; // 树状数组，注意大小要开到 n + m 级别 int n, m; vector<int> all; vector<int> 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 之后要 erase
unique并不会真正缩减数组大小，只是把不重复元素移到前面。如果你忘了 erase，后面all.size()会比实际不重复元素数大，这会导致树状数组的容量判断错误，还可能让二分查找结果偏移。更隐蔽的是，有些编译器环境下lower_bound对于去重不完全的数组依然能返回正确结果，这反而会掩盖问题，让你在不知不觉中埋下 bug。所以我的建议是：写完排序去重后立刻检查 all.size() 是否符合预期。
5.3 二维离散化中的“格子”与“点”
这是进阶内容里最容易翻车的点。在二维平面问题中，如果我们要统计矩形区域的覆盖面积，离散化之后横纵坐标会形成若干“格子”，而不是“点”。一个具体坐标离散化后对应的是“某个边界位置”，而不是“某个格子编号”。
举个例子：一条线段从 x=1 覆盖到 x=3，如果只把 {1, 3} 离散化，那么两个边界之间长度为 3-1=2 的区间被压缩成了一个格子。但如果你把 {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[i+1] - x_idx[i]) * (y_idx[j+1] - 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？后续操作是在“编号”上做，还是需要还原真实数值？把这三个问题想清楚，你就能避开大部分常见的坑。我自己每次写离散化代码之前都会在心里默念一遍这三个问题，这已经成了我的固定习惯，也算是踩了几年坑之后沉淀下来的一点经验。
