一、离散化的概念
离散化是一种将连续数据映射到离散值的过程。它通常用于优化某些算法，尤其是与区间查询相关的问题。
在离散化过程中，我们将一组实数转换为一组整数，使得原始数据的顺序和区间关系得以保留。具体地说，我们将原始数据排序，然后为每个不同的值分配一个整数。这个整数是该值在排序后出现的位置，即离散化后的数值。
假设我们有以下一组实数：{ 3.5 , 2.1 , 5.6 , 1.2 , 3.5 3.5, 2.1, 5.6, 1.2, 3.5 3.5,2.1,5.6,1.2,3.5}。对它们进行排序后，得到 { 1.2 , 2.1 , 3.5 , 3.5 , 5.6 1.2, 2.1, 3.5, 3.5, 5.6 1.2,2.1,3.5,3.5,5.6}。接着，我们可以为每个不同的值分配一个整数，例如：
1.2
→
1
1.2 → 1
1.2→1
2.1
→
2
2.1 → 2
2.1→2
3.5
→
3
3.5 → 3
3.5→3
5.6
→
4
5.6 → 4
5.6→4
最终，我们将原始数据替换为离散化后的整数，得到 { 3 , 2 , 4 , 1 , 3 3, 2, 4, 1, 3 3,2,4,1,3} 。这些整数可以用于解决一些与区间查询相关的问题，例如线段树、树状数组等算法。
二、离散化的模板
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
// 二分求出x对应离散化的值
int find(int x)
{
// 找到第一个大于等于x的位置
int l = 0,r = alls.size() - 1;
while(l<r)
{
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
三、离散化的应用
题目
假定有一个无限长的数轴，数轴上每个坐标上的数都是
0
0
0。
现在，我们首先进行
n
n
n 次操作，每次操作将某一位置
x
x
x 上的数加
c
c
c。
接下来，进行
m
m
m 次询问，每个询问包含两个整数
l
l
l 和
r
r
r，你需要求出在区间
[
l
,
r
]
[l,r]
[l,r] 之间的所有数的和。
输入格式：
第一行包含两个整数
n
n
n 和
m
m
m。
接下来
n
n
n 行，每行包含两个整数
x
x
x 和
c
c
c。
再接下来
m
m
m 行，每行包含两个整数
l
l
l 和
r
r
r。
输出格式：
共
m
m
m 行，每行输出一个询问中所求的区间内数字和。
数据范围：
−
1
0
9
≤
x
≤
1
0
9
−10^9≤x≤10^9
−109≤x≤109
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105
1
≤
m
≤
1
0
5
1≤m≤10^5
1≤m≤105
−
1
0
9
≤
l
≤
r
≤
1
0
9
−10^9≤l≤r≤10^9
−109≤l≤r≤109
−
10000
≤
c
≤
10000
−10000≤c≤10000
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
思路分析
由于
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105 和
1
≤
m
≤
1
0
5
1≤m≤10^5
1≤m≤105 所掉用的数字范围较小，而数轴范围较大，故可以将通过离散化处理，将
−
1
0
9
-10^9
−109 ~
1
0
9
10^9
109范围缩为
1
0
5
10^5
105左右，大大提高效率。
文章来源：https://www.toymoban.com/news/detail-585080.html
代码实现
tip：注意范围问题，s是从1开始的数组，所以可以通过调整二分法，将返回下标都加上1。文章来源地址https://www.toymoban.com/news/detail-585080.html
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 3 * 1e5 + 10;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
// 二分查找
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + ((r - l) >> 1);
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1; // 由于S是从1开始的，所以对应映射位置都往前提一位
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; ++i)
{
int l, r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
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];
for (auto& item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
到了这里，关于离散化（算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
