离散化，这个词第一次见到多半是在算法竞赛的题解里。当时我还在想，这不就是把连续的东西切开吗，有什么好讲的。直到有一次做一道树状数组的题，坐标范围直接给到1e9，数组开不下，排序排不动，这才被现实狠狠教育了一顿。从那以后我才真正明白，离散化不是“切开”，而是“压缩编号”，是把一个稀疏的、巨大的值域映射到一段紧凑的、有序的整数上去，让那些装不下的数据结构能装下，让跑不动的算法能跑动。

这篇文章我打算把离散化讲透，从它到底在解决什么问题说起，再到完整的手写实现、STL写法、常见坑点，最后结合树状数组、并查集这类经典场景，给你一套拿来就能用的方案。不管你是正在刷题准备比赛，还是在工程里遇到超大值域需要处理，这篇应该都能帮上忙。

1. 离散化到底解决什么问题

1.1 值域太大装不下的尴尬

先说一个最简单的场景。假设你有一组数，总共10万个，但每个数的范围在1到1e9之间。现在要统计每个数出现了多少次，你第一反应肯定是开一个数组，下标就是数字本身，数组里存个数。可问题是，数组下标最大只能开到1e9，这在任何一台常规服务器上都不可能分配出这么大的内存，更别说很多题目还只给64MB或256MB。

这种“数量少，范围大”的数据，就是典型的离散化适用场景。10万个不同的数，说到底也只有10万个不同的取值，我完全可以把它们重新编号成1到10万，然后用10万大小的数组去统计，内存问题立刻解决。这个重新编号的过程，就是离散化。

1.2 从连续到离散的思维转变

再往深一层想，离散化的本质是把“值的大小关系”保留下来，而把“值本身有多大”这件事丢弃。比如原来的数是[3, 100, 2, 9999]，离散化之后变成[2, 3, 1, 4]。可以看到，1对应最小的2，2对应次小的3，3对应第三小的100，4对应最大的9999，相对大小关系完全没变，但数值范围从1到9999被压到了1到4。

这个思路在很多算法里都成立。排序需要比较大小，离散化之后比的是新编号；树状数组需要下标从1开始，离散化之后下标刚好满足；二分查找需要有序序列，离散化之后序列天然有序。只要算法依赖的是“大小关系”而不是“具体数值”，离散化就没有副作用。

我甚至见过有人把离散化类比成“给选手重新排号”：原来每个人的身高从1米5到2米1不等，现在按身高从矮到高排，最矮的1号，最高的N号。虽然编号和身高不是同一个东西，但谁比谁高这件事，用编号判断和用身高判断是完全一致的。

1.3 离散化这个术语还有别的含义

聊到这里，必须澄清一下。在算法竞赛和数据结构领域里，“离散化”就是上面说的压缩编号。但在控制理论、数字信号处理领域，“离散化”通常指把连续时间的系统方程转成离散时间的差分方程，比如PID控制器的位置式离散化、数字电源传递函数的离散化，完全是另一码事。

这篇文章讲的是前者，也就是面向算法竞赛和数据处理场景的离散化技术。如果你搜索“离散化”看到的是PID、传递函数、多二阶广义积分器这些东西，那说明你搜到了另一个领域，别搞混了。

2. 离散化的完整实现步骤

2.1 核心三步：排序、去重、二分

离散化在手写的时候，逻辑非常清晰，就三步：

1. 把所有需要用到的原始数值收集到一个数组里。
2. 对这个数组排序，然后去重。
3. 对每个原始值，在去重后的数组里用二分查找找到它的位置，这个位置的下标就是它离散化后的新值。

为什么要排序去重？因为排序之后数组才有序，二分才能生效。去重是因为同一个值应该映射到同一个编号，如果不去重，后面二分查找lower_bound返回的位置是第一个出现的位置，不会重复，但存放的时候会白白浪费空间，而且处理不当还可能造成编号不连续。

举个实际例子。原始数据是[5, 1, 100, 1, 5]，收集到数组a里。先排序，a变成[1, 1, 5, 5, 100]。然后unique去重，得到b = [1, 5, 100]，长度为3。接着对原始数据的每个值做lower_bound查找：5在b中的下标是1，1的下标是0，100的下标是2。于是离散化结果就是[1, 0, 2, 0, 1]。如果题目要求编号从1开始，就再统一加1，变成[2, 1, 3, 1, 2]。

2.2 手写版本的C++代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int origin[MAXN]; // 原始数据 int tmp[MAXN]; // 用于排序去重的副本 int n; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &origin[i]); tmp[i] = origin[i]; } sort(tmp + 1, tmp + n + 1); int m = unique(tmp + 1, tmp + n + 1) - (tmp + 1); for (int i = 1; i <= n; i++) { origin[i] = lower_bound(tmp + 1, tmp + m + 1, origin[i]) - tmp; } for (int i = 1; i <= n; i++) { printf("%d ", origin[i]); } return 0; }

这段代码有一个细节需要注意：lower_bound(tmp + 1, tmp + m + 1, origin[i]) - tmp的结果是一个从1开始的编号，正好符合大多数数据结构对下标从1开始的要求。如果你希望编号从0开始，改成lower_bound(...) - tmp - 1即可。

2.3 用STL简化：lower_bound和unique的组合

很多初学者会被unique的去重逻辑搞晕，因为unique其实不是真正删除元素，它只是把不重复的元素移到前面，返回去重后的末尾迭代器。所以标准用法是先用sort排序，再配合unique得到去重后的长度，最后用lower_bound做查找。

sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());

这两行几乎是所有离散化代码的固定开头。先用sort让所有重复元素聚在一起，再用unique把重复的部分挪到容器末尾，最后erase把多余的部分清掉。这样vec里剩下来的就是从小到大、无重复的“值域字典”。

然后查找编号：

int id = lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;

lower_bound返回的是第一个不小于x的迭代器，减去begin()得到0基下标，加1之后变成1基编号。整个离散化代码，核心就是这四五行，背住就够用了。

2.4 离散化为什么不会丢掉信息

有一个需要想清楚的问题：离散化之后，原数值本身的信息是不是丢了？答案是：丢了，但丢的是“数值大小”这个绝对量，保留的是“相对大小”这个相对量。

对于排序算法、树状数组求逆序对、并查集维护偏序关系这些场景，相对大小就是全部需要的信息。举例来说，求逆序对要判断的就是a[i] > a[j]且i < j，离散化之后编号之间的大小关系依然保持，所以结果完全一样。

但对于需要用到数值差值的场景，比如线段树区间求和、维护区间最大值减最小值，离散化就不适用了。因为离散化之后的相邻编号差值并不等于原始相邻值的差值，原来的[1, 100, 101]离散化成[1, 2, 3]之后，相邻差值从99和1变成了1和1，完全失真。所以离散化前一定要先问自己：我的算法里用到了“差值”吗？用到了就不能离散化，用不到就可以。

3. 离散化的几种常见实现方案对比

3.1 数组去重版：适合竞赛场景

竞赛中最常用的就是第2部分说的sort + unique + lower_bound组合。原因很实在：代码短、运行快、不需要额外依赖。排序的复杂度是O(n log n)，二分每个数据一次是O(n log n)，整体就是O(n log n)，在n到达10万、100万级别的时候完全没问题。

内存占用也小，两个数组存原始值和去重值，下标从1开始，完全契合C风格数组的习惯。我对这个方案的评价就四个字：皮实够用。

3.2 哈希表版：压榨常数性能

如果你需要离散化的量非常大，或者二分查找的常数让你不太满意，还有一种做法：用unordered_map把原始值直接映射到编号。先对去重后的数组遍历一遍，构建哈希映射，然后再遍历原始数据，通过map O(1)查找编号。

sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); unordered_map<int, int> mp; for (int i = 0; i < (int)vec.size(); i++) { mp[vec[i]] = i + 1; } for (int i = 1; i <= n; i++) { origin[i] = mp[origin[i]]; }

理论上单次查找O(1)，总复杂度O(n log n)的瓶颈只剩在排序上。不过unordered_map的常数其实不小，数据量在10万级别时和二分差距不大，数据量到100万以上时哈希表通常更快。代价是内存占用更高，而且哈希冲突在最坏情况下会退化，所以比赛里我一般还是优先二分，遇到时间卡得极紧的题再考虑哈希。

3.3 在线离散化：动态插入怎么办

前面两种都是离线处理，要求你预先知道所有可能的数值。但有的场景是边读入边查询，所有值不可能一开始就全知道，比如交互式问题，或者流式处理数据。

这个时候可以用有序容器动态维护。C++里可以用map<T, int>，每次来一个新值就先查map里有没有，没有就分配一个新编号插进去。查找和插入都是O(log n)，虽然比数组版慢一点，但胜在支持动态增长。

如果是Python场景，可以直接用sortedcontainers这个库，里面有个SortedList，支持有序插入和二分查找，写起来非常舒适。不过要注意，Python的排序和查找常数大，离散化数据量大的时候性能会比较感人，这时候更好的选择是先用pandas或numpy做一次性离线处理。

3.4 到底选哪个：一个经验法则

我的建议很简单：比赛和绝大多数工程场景，默认选sort + unique + lower_bound；如果数据规模极大且性能吃紧，换哈希表；如果是动态流式数据，用map在线维护。如果是在Python里处理数据科学场景，不要自己手写排序去重，直接用pandas的factorize，它天然就是为这种“把类别转编号”的需求设计的。

4. 离散化的典型应用场景

4.1 树状数组求逆序对：最经典的实战

先看一道非常经典的题：给定一个长度为n的排列（或数组），求逆序对数量。树状数组的做法是：从左往右扫描，每扫到一个数x，就用树状数组查询前面有多少个数比x大，再把x对应的位置加1。

如果数组的值域是1到n，直接开树状数组就行。但值域一旦大到1e9，树状数组就无从下手。这时候把原数组离散化，让每个值映射成1到n的编号，再用树状数组，完美解决。这也是离散化最经典、最常考的应用场景。

// 核心代码 int n; vector<int> a, b; // 读入a，b=a，排序去重b // 对a每个元素做离散化 long long ans = 0; for (int i = 1; i <= n; i++) { // 查询已插入的、大于当前编号的元素个数 ans += i - 1 - query(a[i]); update(a[i], 1); }

这里的query(a[i])查的是小于等于a[i]的数量，所以前面已插入总数i - 1减去它就是大于a[i]的数量，即逆序对贡献。

4.2 并查集带偏移的映射问题

另一个常见场景是并查集处理区间覆盖或关系合并问题，其中“点”的编号很大，而实际“不同点”的数量很少。比如有个题目给了一堆区间[ l[i], r[i] ]，需要对区间端点进行并查集合并且判断冲突。如果直接用原始l[i]和r[i]开数组，坐标范围可能到1e9，根本开不下。把l和r的所有值收集起来离散化，再用离散化后的编号作为并查集的点，瞬间把范围压缩到区间数量的2倍以内，问题迎刃而解。

这里有一个关键细节：离散化时，区间端点不仅要包含l[i]和r[i]，如果有需要，还要考虑l[i]-1、r[i]+1这类“边界相邻”的值。否则会出现“原本相邻的点被映射成不相邻”的情况，导致并查集的连通性判断出错。这个坑我踩过不止一次，后面会在常见问题里详细说。

4.3 离线查询中的坐标压缩

还有一种典型场景，是二维平面上的点或者查询。比如给一堆平面上的点，询问某个矩形区域内有多少个点。如果点的横纵坐标范围很大，但点数很少，就可以把x坐标和y坐标分别离散化，然后建一个离散化后的二维前缀和或树状数组。

这种做法的核心在于：我们只关心点在坐标轴上的相对位置，不关心实际坐标的绝对大小，所以可以把所有点投影到压缩后的坐标轴上，再在压缩后的网格上做统计。虽然实现起来比一维复杂，但思路完全一致。

4.4 图像与机器学习里的对应思想

离散化的思想也不只是竞赛专属。图像处理里把灰度值从0到255的连续区间分成若干个等级，就是一次离散化；机器学习里把连续特征切成多个桶做分箱处理，也是离散化。甚至你看到的“MAXVITV2-NANO分类算法”这类图像分类任务里，边界框坐标的量化处理、类别标签的映射，本质上都在用同样的“大值域转小值域”的思路。

反过来，如果你在工程里搜索“离散化”时看到PID控制器的位置式离散化、差分方程、数字电源传递函数实现这些内容，那是把连续系统的微分方程近似成差分方程，核心是采样与近似，和目标映射的离散化思路完全不同，别混淆。

5. 实操过程中的关键细节与代码

5.1 详细实操：从原始数据到离散化结果

我习惯把离散化写成一个函数，方便复用：

vector<int> discrete(vector<int> nums) { vector<int> sorted = nums; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int &x : nums) { x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1; } return nums; }

这个函数的输入是原始数组，输出是离散化后的编号数组。写的时候注意两点：第一，sorted传的是副本，不会修改原数组；第二，lower_bound的结果强制加1，确保编号从1开始。

如果你对性能有更高要求，或者需要多次离散化，可以考虑在全局缓存sorted，避免重复排序。

5.2 处理二维离散化：直接扩展一维思路

二维离散化的思想是分别对x和y坐标独立离散化。对点集(x[i], y[i])，分别收集所有x坐标和所有y坐标，各自做去重排序，然后把每个点的x映射到新的x编号，y映射到新的y编号。

vector<pair<int, int>> points; // 读入points vector<int> xs, ys; for (auto &p : points) { xs.push_back(p.first); ys.push_back(p.second); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for (auto &p : points) { p.first = lower_bound(xs.begin(), xs.end(), p.first) - xs.begin() + 1; p.second = lower_bound(ys.begin(), ys.end(), p.second) - ys.begin() + 1; }

注意，唯一的难点在于：二维离散化之后，原本“x坐标相等”和“y坐标相等”的关系依然保留，但“x=2和x=3之间原本有没有其他点”这种信息会丢失。所以如果想保留“空隙”的影响，有时候需要把相邻坐标之间额外插一个点，这个技巧在扫描线题目里特别有用。

5.3 用Python怎么写：pandas的factorize

在Python里做数据科学或者工程处理，我强烈建议直接用pandas的factorize，它天生就是做离散化的：

import pandas as pd import numpy as np arr = np.array([5, 1, 100, 1, 5]) codes, uniques = pd.factorize(arr) print(codes) # [0 1 2 1 0] print(uniques) # [5 1 100]

注意，pd.factorize默认是按出现顺序编码的，不是按值的大小排序编码。如果你需要按值的大小给编号，先排序再说：

sort_idx = np.argsort(arr, kind='stable') codes = np.empty_like(sort_idx) codes[sort_idx] = np.arange(1, len(arr) + 1)

如果只用一次，直接pd.factorize省事；但如果后续要做排序、比较、二分，最好还是按值排序编码，因为codes与uniques的关系要保证大小顺序一致，否则后续判断可能出错。

5.4 实测离散化前后数据结构对比

以10万个数据点、值域1e9为例，做个简单的对比：

这个表是我实测下来的经验，不是理论值。实际项目中，内存分配器、缓存命中率都会影响最终结果，但大方向的结论不变：离线场景用二分，在线场景只能动态维护。

6. 离散化的常见问题与避坑指南

6.1 去重后序列的长度是不是必须等于元素种类数

是的。n个元素去重后最多有n种，排序+unique出来的长度就是不同值的种类数。在离散化的时候，编号的范围就是1到m（去重后长度）。有些题里会把编号有没有用满作为一个判断依据，比如判断数据是不是连续的，此时m和n的关系就很重要。

6.2 编号从0开始还是从1开始

这个没有标准答案，完全看后续数据结构的要求。

树状数组要求下标从1开始，因为树状数组的lowbit操作在0下标会死循环；很多线段树的写法也从1开始；但普通数组从0开始也能用，只是后面转换麻烦。我的建议是：默认从1开始，因为和数据结构配合更顺畅；如果只是做统计，从0开始也无妨，别换来换去。

6.3 处理区间覆盖时，为什么相邻坐标也要离散化

这个坑极其经典。假设有三个区间：[1, 10], [1, 4], [6, 10]，问有多少个位置被覆盖了至少一次。如果只对端点{1, 10, 4, 6}做离散化，得到1->1、4->2、6->3、10->4，然后统计覆盖情况时发现：区间[1, 4]覆盖编号1到2，区间[6, 10]覆盖编号3到4，看起来中间似乎漏了一段，但实际上原始的数轴上，4到6之间还有5这个点，4->2和6->3之间隔了编号差1的间距，而这个间距里至少有5这个位置没被覆盖。如果直接用离散化后的编号做长度相关的操作，就会把间距当成单位1，导致计数错误。

解决办法是：在做区间覆盖这类涉及“长度”或“间隔”的问题时，除了原始端点，把每个端点的相邻值和端点+1也加入离散化集合。比如在4和6之间插入一个5，这样4->2、5->3、6->4，间距就体现出来了。代价是数据量翻倍，但换来正确性。

6.4 二分边界写错导致死循环或错位

手写二分而不是用lower_bound的时候，最容易出错的是边界条件。比如：

int l = 1, r = m, ans = -1; while (l <= r) { int mid = (l + r) >> 1; if (sorted[mid] >= target) { ans = mid; r = mid - 1; } else { l = mid + 1; } }

这个写法是查找第一个大于等于target的位置。如果写成了if (sorted[mid] > target)，等于排除了等于的情况，最后结果会错位。我建议干脆用STL的lower_bound，别自己写，除非题目卡时间卡到必须手写。

6.5 坐标范围超过int，用long long吗

必须用。原始坐标到1e9是int边界，但如果有加减、偏移、乘以2这类操作，很容易溢出int。离散化本身可以只比较大小不关心差值，但在排序、二分之前如果坐标有运算，提前用long long存好，省得后面处处提防。

6.6 浮点数能离散化吗

能，但比较麻烦。浮点数的问题在于精度，直接排序去重时，1.0000001和1.0000002可能因为精度问题被当成两个不同值，或者反过来被当成同一个值。解决办法是，先用一个误差范围，比如1e-9，把浮点数映射到某个整数区间，再做整数离散化。具体做法是把所有浮点数乘以一个精度倒数，然后四舍五入取整。但这个很tricky，建议能不用浮点就不用浮点。

7. 一个真实项目里的离散化实战

7.1 题目背景：超大值域的区间统计

我去年做了一道题，数据长这样：有n个操作，每个操作要么是“在位置p增加一个值v”，要么是“查询区间[l, r]的和”。n在2e5级别，p、l、r的范围在1到1e9。这个需求你一看就知道，树状数组可以搞，但坐标范围太大，必须离散化。

关键点是：所有操作里的位置p、查询端点l和r都必须收集起来统一离散化，不能只离散化p。因为查询的时候要用到l和r，如果这两个值不在离散化集合里，后面二分查找就找不到了。

7.2 完整代码：树状数组配合离散化

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; long long bit[MAXN * 3]; // 最多n个点，每个操作涉及2个端点，3倍空间 int n; map<int, vector<pair<int, long long>>> ops; struct Query { int l, r; bool isQuery; }; vector<long long> all_coords; vector<Query> queries; vector<pair<int, long long>> add_ops; void bit_add(int idx, long long val) { while (idx < MAXN * 3) { bit[idx] += val; idx += idx & -idx; } } long long bit_sum(int idx) { long long res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & -idx; } return res; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int type; scanf("%d", &type); if (type == 1) { int p, v; scanf("%d%d", &p, &v); add_ops.push_back({p, v}); all_coords.push_back(p); } else { int l, r; scanf("%d%d", &l, &r); queries.push_back({l, r, true}); all_coords.push_back(l); all_coords.push_back(r); } } sort(all_coords.begin(), all_coords.end()); all_coords.erase(unique(all_coords.begin(), all_coords.end()), all_coords.end()); for (auto &op : add_ops) { op.first = lower_bound(all_coords.begin(), all_coords.end(), op.first) - all_coords.begin() + 1; bit_add(op.first, op.second); } for (auto &q : queries) { q.l = lower_bound(all_coords.begin(), all_coords.end(), q.l) - all_coords.begin() + 1; q.r = lower_bound(all_coords.begin(), all_coords.end(), q.r) - all_coords.begin() + 1; printf("%lld\n", bit_sum(q.r) - bit_sum(q.l - 1)); } return 0; }

这段代码里有个地方特别值得注意：所有操作涉及的坐标在第一时间就全部收集到all_coords里了，包括后面查询用的l和r。这是离散化的核心纪律：必须先收集全部数据，再统一排序去重，最后再执行操作。任何“边查边离散化”的操作都会因为编号尚未分配而失败。

7.3 实际运行效果与踩坑记录

我本地随机造了2e5组数据跑了一遍，全程序很快，离散化部分占总时间不到十分之一。之前没把所有查询端点放进去的时候，查询返回的结果偶尔是对的，偶尔是0，排查了半天才发现是查询时lower_bound找不到l和r，返回了end()的位置，编号变成了巨大值，树状数组查询直接越界。后来把所有端点都收集进去，问题立刻消失。

还有一个坑是关于树状数组空间。如果你有n个添加操作和n个查询操作，每个操作最多涉及2个端点，那么坐标总数最多是n + 2n = 3n，所以树状数组开到3n再加一点余量就安全。我一开始只开了2n，提交后RE，查了好久才发现是空间开小了。

7.4 离散化在控制领域的错误理解澄清

写这篇的时候，我特意去看了一眼那些热搜词里的“数字电源传递函数的离散化的实现”“位置式PID用离散化差分方程”“多二阶广义积分器离散化”。这确实是两种完全不同的“离散化”。控制领域说的是把连续系统的微分方程（比如dx/dt = f(x)）转成差分方程（比如x[k+1] = x[k] + T * f(x[k])），核心是采样周期T和数值积分方法的选择，比如前向欧拉、后向欧拉、双线性变换。它关注的是“时间/频率的离散化”，而算法竞赛里的离散化关注的是“值域的压缩映射”。

如果你是在做PID、数字电源、运动控制这些方向，看到“离散化”的时候千万别拿我这篇文章里的sort和unique去套，方向就错了。但如果你是在刷题、处理超大值域的坐标压缩、做树状数组、并查集、二维平面压缩，那这篇文章的方法就是为你准备的。

8. 写在最后的个人经验

离散化这个技巧，说难不难，说简单也简单，但它几乎是所有“值域很大、数量很少”类题目的第一个前置步骤。我自己的习惯是：拿到一道题，先看数据范围，如果发现“n不大但坐标很大”，脑子里第一反应就是离散化。接下来想清楚离散化之后我是要大小关系还是差值关系：只要大小关系，放心离散化；要差值关系，就得想想别的办法。

踩过的坑多了之后，我总结出三条铁律：第一，所有需要的坐标必须一次收集完成，不要漏掉查询和边界；第二，编号从1开始，和数据结构配合更省心；第三，涉及区间覆盖或者网格压缩时，要额外考虑相邻坐标是否需要插入中间点。这三条凡是遵守了，离散化的正确率基本就是100%。

最后再分享一个小技巧。调试离散化代码的时候，不要直接看结果对不对，先输出离散化前后的对照表，看看1号到m号分别对应哪些原值。很多隐蔽的错误，比如去重没做干净、lower_bound写错边界、坐标收集不完整，在这个对照表面前都会现出原形。我用这个办法排查过的问题，没有十次也有八次了，每次都能快速定位到是收集、排序还是查找环节出了问题。