离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。而映射最大的难点是前后的映射关系，如何能够将不连续的点映射到连续的数组的下标。

举例来说，有一些数值，在一个很大的范围里，比如0~10^10的区间，但个数极少。这样一来， 直接开这么大的数组，根本不现实。因为存储的下标实在太大了，所以需要进行映射，而映射的过程就是离散化。

【资料图】

再比如，有一个数组a，分别存储了1，400，8000，6000000。依次将其映射到1，2，3，4，这个过程就是离散化。

离散化的过程中一般会遇到这两个问题，a数组具有重复元素以及如何换算a[i]离散化的值的问题。

解决的方法一般为去重和二分。

区间和 

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

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

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

输入格式

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

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

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

输出格式

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

区间和思路

开辟额外的动态数组add存放要被加上c的位置下标，同时存放要加上去的c（移动下标，改变坐标轴上的c）。

开辟额外的动态数组query存放查询的数组下标的l，r。

因此，需要一个pair<int, int>类型作为动态数组的类型。

（pair是将2个数据组合成一组数据，类似于map<key, value>。pair将一对值组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。）

开辟额外的动态数组alls存放所有数组下标，或者说下标标志，包括询问里的区间的坐标

开辟额外的数组a存取离散化后的数组下标对应的值。

然后开辟额外数组s存取前缀和数组，用于求[l,r] 之间的所有数的和。

简单来说，就是用动态数组来存储下标和需要加上的值，用数组存储真正的数组值。

也就是说，先在动态数组来存储下标和需要加上的值，再在遍历中实现存储真正的数组值。

在依次处理好动态数组的存储后，进行排序和去重以便更好的实现二分（二分查找需要考虑序列中存在具体解以及序列必须有序）。

在遍历中，先将alls的值依次插入值数组a，即先用二分查找（提高效率）处理x，再加上c（前者为.first，后者为.second）。再进行前缀和求取。

最后，利用前缀和求取区间和（区间和就是前缀和来求的某一段和。采用前缀和思想来提高效率）。

过程中，对alls的改动就是离散化的过程（存储下标）。

区间和过程

1.读入和输入。将每次读入的位置x和加数c存到到add中，将每次读入的位置x存到到alls中，将每次读入的左下标l和右下标r存到到query中。

2.进行排序、去重。

3.遍历，完成在离散化的数组映射到的a数组中进行加上c的操作（利用find函数）。

4.预处理前缀和s数组。

5.通过遍历query，完成求区间[l,r]的和。

alls.push_back(l); alls.push_back(r); 的用处在于l与r这两个下标上由于未必存取了相关值，因此在将add中存储到alls里的时候，该位置很可能为空。而二分查找需要一个确定的范围，所以先加上，而该下标已经存储的话，则由最后进行排序去重部分进行消除。

排序与去重中，unique(alls.begin(), alls.end())负责去重，alls.erase(unique(alls.begin(), alls.end()), alls.end())负责去除去重后遗留的不存在值得数组。

疑惑，其实并没有完全学懂，就是尽己所能的记下来先。

关键词： SECOND UNIQUE FIRST FIND 提高效率 数据类型 举例来说 简单来说 这样一来 也就是说