离散化（特指整数离散化）

在算法学习中，我们常会遇到这样的场景：数据范围极大（比如1e9），但实际用到的数据量却很小（比如1e5），直接用数组下标存储会造成巨大的空间浪费。这时候，离散化算法就成了高效解决这类问题的方法。

一、定义

是 将大范围的、分散的、稀疏的数据，映射到小范围的、连续的、密集的索引上，本质是“压缩范围、保留相对大小关系”。

注意：离散化只关注数据的相对大小，不改变数据之间的大小关系——原来大的数，映射后依然大；原来相等的数，映射后依然相等。

二、实现步骤

步骤1：准备原始数据，提取所有需要离散化的值。

收集所有“需要参与映射”的数据,确保不遗漏任何一个需要处理的值。

//原始数据
vector<int> r_data = {100, 5, 20, 10000, 3000000};
//存储所有待离散化的值在数组中
vector<int> alls = r_data;

步骤2：排序 + 去重

对提取出的列表排序，然后去掉重复元素——这样就能得到一个“唯一、有序”的列表，每个元素对应一个离散化后的索引。

//对所有待离散化的值进行排序
sort(alls.begin(), alls.end());
//去掉重复元素
alls.earse(unique(alls.begin(), alls.end()), alls.end());

步骤3：映射

将原始数据中的每个值，映射到它在“去重排序后列表”中的索引（通常从1开始，方便后续前缀和/差分操作，避免下标为0的麻烦）。

映射的实现有两种方式：

//方法1：遍历数组
int find(int x){
for(int i = 0; i < alls.size(); i++){
if(alls[i] == x){
return i + 1;
}
}
}
//方法2：二分法求出对应离散化后的值
//初始化左右区间
int find(int x){
int l = 0, r = alls.size() – 1;
while(l < r){
int mid = (l + r) / 2;
if(alls[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
return l + 1;
}

三、例题:区间和

题目描述（题目来源于AcWing）

思路

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// pair<int, int> 是一种能存储两个整数（第一个和第二个）的结构，就像一对数。
// 给 pair<int, int> 起了一个别名叫做 PII
typedef pair<int,int> PII;

const int N = 3e5 + 10;
long long a[N], s[N];
long long n,m;

//存储待离散化的值—-用于映射
vector<int> alls;
//定义了两个变量 add 和 query，它们都是 vector，里面存放的元素类型是 PII
vector<PII> add,query;

//二分查找在alls中找到某个原始坐标x的离散化后的坐标
int find(int x){
int l = 0, r = alls.size() – 1;
while(l < r){
int mid = (l + r) / 2;
if(alls[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
return l + 1;
}

int main(){
cin>>n>>m;

//输入操作
for(int i = 0; i < n; i++){
int x, c;
cin>>x>>c;

//把x和c放入add中
add.push_back({x,c});
//把输入的数据放入vector<int> alls数组中
alls.push_back(x);

}
//输入询问区间
for(int i = 0;i < m; i++){
int l, r;
cin>>l>>r;

//把l,r放入query中
query.push_back({l,r});

//把l,r放入alls中
alls.push_back(l);
alls.push_back(r);
}

//排序
sort(alls.begin(), alls.end());
//去重
alls.erase(unique(alls.begin(), alls.end()), alls.end());

//遍历add容器的值—–使得对应位置x加上c
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}

//计算离散化后的前缀和
for(int i = 1; i <= alls.size(); i++){
s[i] = s[i – 1] + a[i];
}

//遍历query容器—-计算区间和
for(auto item : query){
int l = find(item.first);
int r = find(item.second);
int sum = s[r] – s[l – 1];
cout<< sum <<endl;
}
return 0;
}

四、总结

• 离散化是缩小数据规模、优化空间时间的利器。

• 掌握排序、去重、二分查找三要素即可快速实现。