算法里面的离散化

一、离散化（discretization）在算法和数据结构中指的是将连续的输入数据映射到离散的值或者范围，从而使得处理和计算变得更高效。通常用于处理大范围或者无限可能的输入，以便将其转化为有限的、可以有效处理的范围。

离散化的定义

离散化的主要目的是将连续的值或大范围的值映射到一个有限的集合中，以便进行高效的存储和处理。这通常通过对连续的数据进行排序、分组、或者映射来实现。

离散化的步骤

排序和编号：对所有唯一的连续值进行排序，然后为这些值分配一个唯一的编号。
映射：使用一个映射函数，将原始数据的每个值转换为新的编号或索引。

应用场景

区间压缩：在处理大范围的整数值时，通过离散化可以将这些值映射到一个较小的范围。例如，处理1到10000的值时，可以将它们映射到1到100的范围内。
数据结构优化：在某些数据结构中（如树状数组或线段树），需要将离散化后的值作为索引来优化查询和更新操作。

离散化在以下方面有应用：

机器学习：将连续特征转换为离散类别，简化模型处理，例如将年龄分段成“青年”、“中年”、“老年”。
图像处理：将图像数据的连续像素值转换为离散的色彩级别，提高处理效率。
数据压缩：将连续信号如音频或视频离散化，以减少存储需求。
数据库设计：将连续数据映射到离散值，用于更高效的数据索引和查询。

这些应用帮助简化计算、提高效率或改善模型性能。

例子

例子 1：区间压缩

假设有一组连续的坐标值：[100, 150, 300, 600, 900]。我们希望将这些值映射到更小的范围。

排序和编号：
- 排序后的值：[100, 150, 300, 600, 900]
- 对这些值进行编号：100 -> 1, 150 -> 2, 300 -> 3, 600 -> 4, 900 -> 5
映射：
- 原始值 100 映射到编号 1
- 原始值 150 映射到编号 2
- 原始值 300 映射到编号 3
- 原始值 600 映射到编号 4
- 原始值 900 映射到编号 5
这样，我们就将原始的连续值压缩到了 [1, 2, 3, 4, 5]，这使得后续的数据结构（如线段树或树状数组）的操作更为高效。

例子 2：二维离散化

假设有一组二维坐标值：[(10, 20), (15, 30), (30, 60)]。我们需要将这些坐标值离散化。

提取和排序：
- X轴坐标：[10, 15, 30]
- Y轴坐标：[20, 30, 60]
- 对X轴坐标编号：10 -> 1, 15 -> 2, 30 -> 3
- 对Y轴坐标编号：20 -> 1, 30 -> 2, 60 -> 3
映射：
- (10, 20) 映射到 (1, 1)
- (15, 30) 映射到 (2, 2)
- (30, 60) 映射到 (3, 3)
这样，我们将原始的连续坐标转换成离散的坐标，对数据结构的处理（如二维树状数组）将更加高效。

总结

离散化的关键是将原始的、可能是连续或无限范围的数据，转化为有限且可处理的编号或索引。这样不仅优化了存储空间，也提高了数据处理的效率。

二、在算法中，“映射”是指将一个集合中的每个元素通过某种规则或函数转换为另一个集合中的元素的过程。这一概念广泛应用于数据处理、函数设计和数据结构中。以下是映射的详细解释：

1. 基本定义

映射可以被视为一个函数 ( f: A \rightarrow B )，其中 ( A ) 是定义域，( B ) 是值域。对于定义域中的每个元素 ( a \in A )，映射函数 ( f ) 将其转换为值域中的元素 ( b \in B )。形式上，这可以表示为 ( f(a) = b )。

2. 示例

数学中的映射：一个简单的数学映射是 ( f(x) = x^2 )，它将每个实数 ( x ) 映射到它的平方 ( x^2 )。
数据结构中的映射：在哈希表中，映射是通过哈希函数将键（key）映射到对应的值（value）。例如，键 "name" 可能映射到值 "Alice"。

3. 应用

数据转换：在数据处理过程中，可以将数据从一种格式转换为另一种格式。比如，映射函数可以将用户输入的字符串转换为对应的内部数据结构。
离散化：在离散化过程中，映射用于将连续的数据转换为离散的值。例如，将地理坐标映射到一个有限的网格系统中。

4. 复杂映射

映射不仅限于一对一关系，还可以是多对一（多个输入映射到一个输出）或一对多（一个输入映射到多个输出）。例如，在关系数据库中，某一用户ID可能映射到多个订单记录。

5. 映射的属性

单射（Injective）：每个定义域的元素映射到值域中唯一的元素，不存在不同的输入映射到相同的输出。
满射（Surjective）：定义域中的每个元素都映射到值域中的某个元素，使得值域中的每个元素至少被映射一次。
双射（Bijective）：既是单射又是满射，即每个定义域的元素都有唯一的值域元素，且值域中的每个元素都有唯一的定义域元素。

映射在算法中扮演着重要角色，它使得数据转化、存储和处理变得更加系统化和高效。

了解了什么是离散化和映射，接下来直接开始做题，用题目实践才是最好的。

题目：区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n次操作，每次操作将某一位置 x上的数加 c。

接下来，进行 m次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

$-10^{9}$ ≤x≤ $10^{9}$ ，
1≤n,m≤ $10^{5}$ ,
$-10^{9}$ ≤l≤r≤ $10^{9}$ ,
−10000≤c≤10000

输入样例：

输出样例：

8
0
5

离散化的特点：
值域大，个数少。
可以把这n个数映射到它的下标。
常见的问题：
1. 数组a中有重复元素（去重）
2. 如何算出 $a_{i}$ 映射后的值？（二分）

此题把下标映射后前缀和求解即可。

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;
typedef pair<int,int> PII;/*定义pair<int,int>类型为PII，就相当于取了一个别名，就是方便使用的时候不输入那么复杂又长的东西。*/
const int N=3e5+10;
/*因为有三个坐标，所以是用的3e5+10的范围。
输入的n个x，m个l,r，就是n+2m个坐标，因为n和m都是10的五次方，所以就是3乘10的5次方，多10是故意开的，害怕越界嘛。*/
int a[N],s[N];
/*这个就是求的区间和，只不过前面还有些步骤，所以这个a[N]数组是存储的值，不是坐标哈；s[N]
还是和前缀和一样，是放的前缀和的值。*/
vector<PII> add,query;
/*观察题目得到，输入的位置x和插入的值c，与后面输入的区间两个边界l,r一样，都是一次输入一对
的数进去，所以这里定义了一个PII类型的vector，来存储要操作的东西。这里面add是存储插入的位置x和值c，而query是查询区间，并求出指定区间的和，所以query存储的是边界l，r的位置*/
vector<int> alls;
/*alls是存储所有的位置的，不管是刚开始的x，还是l,r都存在里面，后面会操作的，很有用处。记住，vector是c++里面的可变数组，所以在进行和数组类似的操作时，也可以像数组那样使用，切记。*/int find(int x){int l=0,r=alls.size()-1;while(l<r){int mid=l+r>>1;//这里是整数，没有小数，所以可以用位运算。if(alls[mid]>=x)  r=mid;//二分的第一个模板，相当于求最小值的那个，不用加1。else l=mid+1;}return r+1;//这里你写l+1也可以，反正最后二分l是约等于r的，都可以。/**注意返回的是r+1，就是最低是返回1，因为我要求前缀和，所以就这样。/
}
/*这个函数是利用的二分查找，来查找x在alls可变数组里面的位置，也就是x在alls可变数组的数组下标是多少。这其实就是离散化了，alls数组在之前的操作后，已经变得井然有序，每一个输入的坐标值x,l,r在alls里面都有对应的位置，这就已经将原来范围大，数目少且离散，不好处理的坐标给放在了alls数组里面，所以要注意，这个alls数组里面存的是坐标，如果要求对应的值的话，那么就是，例如：要想查询x位置上的值的话，那么就是：1、先找到x这个坐标在alls数组里面的哪个位置，对应的是alls数组的哪个下标。 2、找到了以后，就能迅速的在alls数组里面找到x坐标所在的位置。 3、找到位置后就直接能找到x所对应的值了。   这就是离散化：1、vector存输入的位置坐标；2、在这个vector里面找到需要的位置坐标。
3、找到以后就可以像之前那样正常操作了，想查值就查值，想求前缀和就求前缀和。*/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);}
/*输入n,m，并且输入x，c，这x,c是插入所需要的值，所以将这两个值存到add这个vector里面。然后顺便把位置x存入alls这个可变数组里面。*/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);}
/*输入l,r，并将后面查询求前缀和所需要的值l,r给存入到query这个vector里面去，同时，l,r这两个表示位置的数，也全部存到alls这个可变数组内。*/    sort(alls.begin(),alls.end());//排序alls里面的所有坐标值alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重并调整里面的坐标值。
/*所有输入的关于位置的数，也就是所谓的坐标，已经排序去重并调整大小了，经过了这两步，得到的是
有序的，且中间没有空位的，新的alls可变数组，这对于后面的离散化是很重要的。*/    for(auto item:add){int x=find(item.first);//找x这个坐标在alls数组里面的数组下标是多少。a[x]+=item.second;//在alls数组里面找到x所在的位置后，就直接执行c的插入操作就可以了。}//插入操作for(int i=1;i<=alls.size();i++)  s[i]=s[i-1]+a[i];//注意i<=alls.size()，是从下标1开始的，不是0.
/*这里还是和求前缀和是一样的，在求前缀和之前都要定义一下前缀和的表示，在我看来就是定义一种性质嘛，注意这里是i从1开始，不从0开始是为了避免边界问题。*/for(auto item:query){//这个不一定要写成item，随便写自己喜欢的单词就好，不影响的。int l=find(item.first),r=find(item.second);//分别求l,r在alls数组里面的位置。printf("%d\n",s[r]-s[l-1]);//这就是求前缀和，直接用公式就可以，这是一维前缀和哦。}//查询并求前缀和的操作/*这里面的first,second就是键值，因为我的add和query的vector都是PII类型的，也就是pair<int,int>类型的，就拿这里来说，这里query的item.first指的是输入的l，而item.second指的是输入的r。*/return 0;
}