本课时有配套视频讲解，购买后即可观看（永久有效）
离散化
一、课上练习
编程练习
- 贴海报：L50003
二、知识总结
✨ 核心思想
离散化（Coordinate Compression / Discretization）是一种将大范围的数据映射到小范围连续整数的预处理技巧。
核心场景：当数据的值域很大（如 $10^9$）但数据量较少（如 $10^5$），我们无法开一个 $10^9$ 大小的数组，但可以将这些数据排序去重后重新编号为 $1, 2, 3, \ldots$，使得值域缩小到数据量级别。
离散化保留了数据之间的相对大小关系，丢弃了绝对值信息。这在以下场景中非常有用：
- 树状数组（BIT）/ 线段树需要以值作为下标
- 区间操作中坐标范围过大
- 需要对值域进行桶排序或计数
✨ 算法原理
标准流程
- 收集：将所有出现的值收集到一个数组中
- 排序：对收集的值进行排序
- 去重：去掉重复值
- 映射：用二分查找将原始值映射为离散化后的编号
两种离散化方式
保序离散化：映射后的编号保持原始值的大小顺序（最常用）
紧凑离散化：映射后的编号连续无间隔，从 1 开始
✨ 代码实现
标准离散化模板
discretize_basic.cpp
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7 int n;
8 cin >> n;
9 vector<int> a(n);
10 for (int i = 0; i < n; i++) cin >> a[i];
11
12 // 第一步：复制一份用于离散化
13 vector<int> sorted_a(a.begin(), a.end());
14
15 // 第二步：排序
16 sort(sorted_a.begin(), sorted_a.end());
17
18 // 第三步：去重
19 sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
20
21 // 第四步：映射（用 lower_bound 二分查找）
22 // 离散化后的值从 1 开始
23 for (int i = 0; i < n; i++) {
24 a[i] = lower_bound(sorted_a.begin(), sorted_a.end(), a[i])
25 - sorted_a.begin() + 1; // +1 使编号从1开始
26 }
27
28 // 输出离散化结果
29 cout << "离散化后: ";
30 for (int i = 0; i < n; i++) cout << a[i] << " ";
31 cout << endl;
32 cout << "值域大小: " << sorted_a.size() << endl;
33
34 return 0;
35}封装为函数
discretize_function.cpp
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// 离散化工具类
7struct Discretizer {
8 vector<int> vals; // 排序去重后的值
9
10 // 添加需要离散化的值
11 void add(int x) { vals.push_back(x); }
12
13 // 构建离散化映射
14 void build() {
15 sort(vals.begin(), vals.end());
16 vals.erase(unique(vals.begin(), vals.end()), vals.end());
17 }
18
19 // 查询离散化后的编号（从1开始）
20 int query(int x) {
21 return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
22 }
23
24 // 离散化后的值域大小
25 int size() { return vals.size(); }
26
27 // 根据离散化编号还原原始值
28 int restore(int id) { return vals[id - 1]; }
29};
30
31int main() {
32 int n;
33 cin >> n;
34 vector<int> a(n);
35 Discretizer disc;
36
37 for (int i = 0; i < n; i++) {
38 cin >> a[i];
39 disc.add(a[i]);
40 }
41 disc.build();
42
43 for (int i = 0; i < n; i++) {
44 int original = a[i];
45 int mapped = disc.query(a[i]);
46 cout << original << " -> " << mapped << endl;
47 }
48
49 return 0;
50}离散化 + 树状数组求逆序对
discretize_bit_inversions.cpp
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6typedef long long ll;
7const int MAXN = 500005;
8
9// 树状数组
10int bit[MAXN];
11int bit_n;
12
13void bit_update(int i, int val) {
14 for (; i <= bit_n; i += i & (-i))
15 bit[i] += val;
16}
17
18int bit_query(int i) {
19 int sum = 0;
20 for (; i > 0; i -= i & (-i))
21 sum += bit[i];
22 return sum;
23}
24
25int main() {
26 int n;
27 cin >> n;
28 vector<int> a(n);
29 for (int i = 0; i < n; i++) cin >> a[i];
30
31 // 离散化
32 vector<int> sorted_a(a.begin(), a.end());
33 sort(sorted_a.begin(), sorted_a.end());
34 sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
35 bit_n = sorted_a.size();
36
37 for (int i = 0; i < n; i++) {
38 a[i] = lower_bound(sorted_a.begin(), sorted_a.end(), a[i])
39 - sorted_a.begin() + 1;
40 }
41
42 // 从右到左扫描，树状数组维护已出现的值
43 ll inversions = 0;
44 for (int i = n - 1; i >= 0; i--) {
45 // 查询比 a[i] 小的已出现元素个数
46 inversions += bit_query(a[i] - 1);
47 // 将 a[i] 加入树状数组
48 bit_update(a[i], 1);
49 }
50
51 cout << "逆序对数量: " << inversions << endl;
52 return 0;
53}离散化 + 区间覆盖
discretize_interval.cpp
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7 int n;
8 cin >> n;
9 vector<int> L(n), R(n);
10
11 // 收集所有坐标
12 vector<int> coords;
13 for (int i = 0; i < n; i++) {
14 cin >> L[i] >> R[i];
15 coords.push_back(L[i]);
16 coords.push_back(R[i]);
17 coords.push_back(R[i] + 1); // 右端点+1，处理区间端点
18 }
19
20 // 离散化
21 sort(coords.begin(), coords.end());
22 coords.erase(unique(coords.begin(), coords.end()), coords.end());
23 int m = coords.size();
24
25 auto getId = [&](int x) {
26 return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
27 };
28
29 // 差分数组标记被覆盖的区间
30 vector<int> diff(m + 1, 0);
31 for (int i = 0; i < n; i++) {
32 int l = getId(L[i]);
33 int r = getId(R[i]);
34 diff[l]++;
35 diff[r + 1]--;
36 }
37
38 // 统计被至少一个区间覆盖的总长度
39 ll totalLen = 0;
40 int cnt = 0;
41 for (int i = 0; i < m; i++) {
42 cnt += diff[i];
43 if (cnt > 0 && i + 1 < m) {
44 totalLen += coords[i + 1] - coords[i];
45 }
46 }
47
48 cout << "被覆盖的总长度: " << totalLen << endl;
49 return 0;
50}✨ 执行示例
原始数据：a[] = {100, 3, 100, 50, 3, 999}
1第一步 - 收集: [100, 3, 100, 50, 3, 999]
2第二步 - 排序: [3, 3, 50, 100, 100, 999]
3第三步 - 去重: [3, 50, 100, 999]
4
5映射关系:
6 3 → 位置 0 → 编号 1
7 50 → 位置 1 → 编号 2
8 100 → 位置 2 → 编号 3
9 999 → 位置 3 → 编号 4
10
11第四步 - 映射原数组:
12 a[0] = 100 → lower_bound 找到位置 2 → 编号 3
13 a[1] = 3 → lower_bound 找到位置 0 → 编号 1
14 a[2] = 100 → 编号 3
15 a[3] = 50 → 编号 2
16 a[4] = 3 → 编号 1
17 a[5] = 999 → 编号 4
18
19离散化结果: [3, 1, 3, 2, 1, 4]
20值域从 [3, 999] 缩小为 [1, 4]✨ 解题步骤详解
何时需要离散化
- 值域 >> 数据量：如值在 $[-10^9, 10^9]$，但只有 $10^5$ 个数
- 需要以值为下标：树状数组、线段树等数据结构要求下标连续且较小
- 坐标压缩：二维平面上的点坐标范围很大
完整解题流程
- 分析数据范围：确认值域是否需要离散化
- 收集所有关键值：注意是否需要额外加入端点（如 $x-1$, $x+1$）
- 排序去重：
sort+unique+erase - 建立映射：
lower_bound二分查找 - 在离散化后的值域上操作：BIT、线段树等
需要注意的细节
- 区间问题中加入额外端点：如区间 $[l, r]$，可能需要加入 $l-1$ 或 $r+1$
- 不同题目的编号起点：有的从 0 开始，有的从 1 开始
- 是否需要还原：某些题目需要从离散化编号还原回原始值
✨ 常见错误
- 忘记去重：排序后不调用
unique，导致映射错误 unique后忘记erase：unique只是把重复元素移到末尾，需要erase删除- 映射时用了
upperbound而非lowerbound：会导致编号偏移 - 忘记收集所有需要的值：如区间问题中只收集了左端点忘了右端点
- 编号起点搞错：树状数组通常下标从 1 开始，要
+1 - 离散化后数组大小估计错误：去重后大小可能远小于原始数据量
✨ 算法评价
时间复杂度
| 步骤 | 时间 |
|---|---|
| 排序 | $O(n \log n)$ |
| 去重 | $O(n)$ |
| 单次映射查询 | $O(\log n)$ |
| 全部映射 | $O(n \log n)$ |
| 总计 | $O(n \log n)$ |
空间复杂度
$O(n)$，存储排序去重后的数组。
适用场景总结
| 问题类型 | 离散化 + 配合 |
|---|---|
| 逆序对 | 树状数组 |
| 区间查询 | 线段树 |
| 区间覆盖长度 | 差分 + 离散化 |
| 二维偏序 | 排序 + 树状数组 |
| 矩形面积并 | 扫描线 + 线段树 |
离散化本身不是算法，而是一种预处理技巧，它使得许多需要在大值域上操作的算法成为可能。