关于离散化，OIWIKI上是这么解释的:
????????通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。
用再通俗的话来讲，就是用下标替代原数值，解决一些特定问题；
什么样的特定问题呢？
影响结果的只有原数值的相对大小且原数值分布的比较稀疏（或者说差距比较大）
即 相对大小+差距大
比如给出3个坐标，1，100000，1000000000，其中每个坐标上分别对应一个权值a,b,c，其余没提到的坐标上对应的权值均是0；
那么如果我要求坐标区间内[l,r]的和，那么很显然，这是一个很明显的前缀和问题。
容易想到，我们创建一个数组，预处理后作一个前缀和数组，就可以解决问题了；
可是问题在于，当坐标过大的时候，数组没办法开那么大，即开头提到的：
自身无法作为数组的下标。
那么，于是，就有了离散化。
离散化本质上是一种hash
原因在于，我们可以把数值映射成坐标
即用坐标替代数值，数值的相对大小表现为坐标的相对大小；
离散化操作通常需要先排序，然后去重，然后得到正确的映射。
所以，讲到这里，可以把离散化理解为一种映射（只不过需通过一些操作才能获得正确映射）。
以Acwing 802区间和为例，以经典例题的角度展开叙述：
802. 区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是?0。???????
现在，我们首先进行?n?次操作，每次操作将某一位置?x?上的数加?c。
接下来，进行?m?次询问，每个询问包含两个整数?l?和?r，你需要求出在区间?[l,r] 之间的所有数的和。
输入格式
第一行包含两个整数?n?和?m。
接下来?n?行，每行包含两个整数?x?和?c。
再接下来?m?行，每行包含两个整数?l 和?r。
输出格式
共?m?行，每行输出一个询问中所求的区间内数字和。
数据范围
?109≤x≤109
1≤n,m≤105
?109≤l≤r≤109
?10000≤c≤10000
问题分析：
很显然，下标的大小达到了10的9次方，显然无法直接开等大的数组，但是我们可以离散化！
还是前面那句话！离散化就是把数值映射成下标。
????????那么可以看到，有n行输入，输入了n个坐标，和与其坐标对应的权值（应该累加的值）；
那么考虑最坏的情况，如果这n个坐标互异，那么我们也仅仅需要开1e5大小的数组；
可以发现空间大幅度减小！
? ? ? ? 接下来的m行输入，每一行输入一对(l,r），也就是一对坐标x1,x2。由于我们最终要求[x1,x2]内的元素和，所以我们关心x1和x2上的权值，因而有必要在离散化的时候把x1,x2也进行一个映射。同样的，若这2m个坐标互异，2m<=2*1e5, 那么我们再开2*1e5大小的空间，也足以应付！（使得每个坐标都是一个唯一确定的下标与之对应）
因而，我们开一个坐标数组alls,对于每一个坐标，存入alls[i]；
等价于alls[i]这个坐标映射成了下标i！
那么该如何实现这个操作?
很简单，我们先读入所有的坐标,push_back到alls数里面，然后sort一遍
就可以实现 若i<j,必定alls[i]<alls[j]的逻辑关系，即开头提到的用坐标替代数值，数值的相对大小表现为坐标的相对大小；
然后我们需要去重，这一步可能比较突然，后面会解释。（其实当前可以这么理解，既然是映射，我们设坐标为x，x通过映射法则映射成f(x)，那么根据数学知识，我们直到一个x仅且对应一个f(x)，而一个f(x)是可以对应多个x）
所以目前，我们就形成了一个映射体系，即坐标和下标的一 一对应关系，用数组alls体现.
当坐标离散化后，由于我们想求的是元素和，那么需要关注权值；
权值仅出现在输入的时候，而我们希望把权值放到对应的坐标上，
换句话说，我们更希望，把权值放到对应的坐标所对应的离散化下标上。
但是，我们无法做到一边读入一边离散化，而我们上述的希望是基于离散化工作完成的基础上，那么，我们需要一个容器，暂时存下输入，vector<pair<int,int>> add，即操作向量
同样的，我们再准备一个操作向量,vector<pair<int,int>>query，暂时地把“询问”存起来。
当读入完毕后，我们就需要把权值放上去，因而离不开一个原数组（这里有暗示了，和前缀和相对应），我们创建它。
遍历add,每个元素的第一个位置存的是坐标，第二个元素存的是当前应该累加的值c；
那么该如何把坐标转化成对应的下标？由于alls这个坐标数组是排好序的且是一 一对应(这时候你就知道为什么要去重了)，我们可以二分查找，找到坐标对应的下标i,执行a[i]++c；
那么，遍历完后，a[i]代表某个坐标上的权值（某个坐标：下标i相对应的坐标）；
所以我们到这里就实现了，把权值放到对应的坐标所对应的离散化下标上。
那么接下来，原数组创建好了，下一步就是求终极任务：元素和
在原数组的基础上，我们开一个前缀和数组s（下标从1开始，避免特判)
那么s[i]=a[1]+a[2]+..a[i]（1<2<...i，所对应的下标x1<x2<..xi）
s[i]可以表述为数轴上x1+x2+..xi的和
因而给定一组(i,j)，我们列：s[i]-s[j-1] = a[j]+a[j+1]...a[i](每个元素都非0)（xj<xj+1<...xi)
表述为数轴上[xj，xi]的元素和，（非0的元素和+0的元素和）
这时候利用我们之前开的query数组,读入l,r；
由于l,r是真实的坐标，我们需要将其映射到下标，还是用到二分!
把[l,r]转化为[j,i]，所以求xj+...xi = aj+...ai = s[i] - s[j-1],大功告成！
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e5+10;
int a[N],s[N];
typedef pair<int,int>PII;
vector<PII> add,query;
vector<int>alls;
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;
else l = mid+1;
}
return r+1;//找到第一个大于等于x的下标
}
int main()
{
int n,m;
cin >> n >> m;
int x,c;
for (int i = 1;i <= n;i++)
{
cin >> x >> c;
alls.push_back(x);
add.push_back({x,c});
}
int l,r;
for (int i = 0;i<m;i++)
{
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 i:add)
{
int j = find(i.first);//使得下标x先映射到下标，再在下标数组中运算
a[j]+=i.second;
}
for (int i = 1;i<=alls.size();i++) s[i] =s[i-1]+a[i];
for (auto i:query)
{
int p = find(i.first),q = find(i.second);
cout<<s[q] - s[p-1]<<endl;
}
}
?
我是小郑，正在奔赴热爱，奔赴山海，体会数学和算法之美~???????