数值本身可能大到离谱，但真正出现过的数值没几个——只保留"排第几"这个相对顺序，把天文数字压缩成 1~n 的连续下标。
16.2、16.3 节要学的树状数组、线段树，通常要求维护的下标是 1~n 这样连续的整数——数组开多大、循环怎么写，都建立在"下标范围不大"这个前提上。但实际题目里，数据的取值范围可能非常夸张（比如坐标范围是 1~10⁹），而数据的个数却很少（比如只有 10⁵ 个数）。如果直接按数值大小开数组，要么开不下（内存不够），要么绝大部分空间都在浪费（真正用到的值稀稀拉拉分布在一个巨大的范围里）。
离散化解决的正是这个矛盾——把一堆"数值很大、但个数不多"的数，压缩成 1~n 的连续整数，压缩前后，数值之间原本的大小顺序保持不变。
很多题目真正关心的并不是某个数具体是多少，而是它在所有出现过的数里排第几（比如"求区间内比它小的数有多少个"，只需要知道相对顺序，不需要知道具体数值）。离散化就是利用这一点：把原始数组排序、去重后，每个数在这个"去重排序后的数组"里的位置（下标），就是它离散化之后的新值——这个新值一定落在 1~n（n 是去重后的个数）范围内。
| 步骤 | 做什么 |
|---|---|
| ① 复制 | 把原数组复制一份，准备排序（保留原数组不动，后面还要用） |
| ② 排序 | 对复制的数组从小到大排序 |
| ③ 去重 | 相同的数值只保留一份（常用 unique） |
| ④ 查名次 | 对原数组里的每个数，在"排序去重后的数组"里用二分查找（lower_bound）找到它的位置，就是离散化后的新值 |
原数组 a = [100, 5000000, 3, 100, 50]——数值分布得很散，但只有 5 个数：
3 一路跨到 5000000 的数值范围，压缩成了 1~4 的连续整数。两个 100（a[0] 和 a[3]）离散化后都是排名 3——大小关系完全保留：谁在原数组里更大，离散化后的排名也更大；相同的数，排名也相同。| 1 | int a[MAXN], n; // 原数组 |
| 2 | vector<int> b; // b：排序去重后的"离散化字典" |
| 3 | |
| 4 | void Discretize() |
| 5 | { |
| 6 | b.assign(a + 1, a + 1 + n); // ① 复制一份原数组 |
| 7 | sort(b.begin(), b.end()); // ② 排序 |
| 8 | b.erase(unique(b.begin(), b.end()), b.end()); // ③ 去重（unique 把重复项挪到末尾，erase 删掉） |
| 9 | |
| 10 | for (int i = 1; i <= n; i++) |
| 11 | a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; // ④ 二分查名次，+1 让排名从 1 开始 |
| 12 | } |
lower_bound 在这里做的事情，就是"查字典"：lower_bound(b.begin(), b.end(), a[i]) 在有序数组 b 里，找到第一个"大于等于 a[i]"的位置——因为 a[i] 一定在 b 里出现过（b 就是从 a 复制来的），这个位置对应的正是 a[i] 本身。返回的是一个迭代器，减去 b.begin() 转换成从 0 开始的下标，再 +1 让排名从 1 开始（方便后续直接当树状数组、线段树的下标使用）。排序 O(n log n)；对每个数做一次二分查找 O(log n)，一共 n 次，合计 O(n log n)。整体离散化的时间复杂度是 O(n log n)，空间上多开一个大小为 n 的 b 数组，O(n)。
unique，数组 b 里会保留重复的数值，lower_bound 依然能正确工作（原理不受影响），但 b 的长度不再等于"不同数值的个数"，后续树状数组、线段树开的数组大小、下标范围都会跟着算错，很容易引发越界之类的问题。100 变成了排名 3，如果题目后续还需要"排名 3 对应的原始数值是多少"，必须自己保留 b 这个数组（b[排名-1] 就是原始数值），不能只保留离散化后的结果就把原始信息丢掉。b：vector 不会像普通数组那样"用完自动清零"，如果每组数据前忘记 b.clear()，上一组遗留的数据会混进这一组的离散化结果里，导致排名算错。