应用于数字取值范围很大，但数字个数很少的情况，原理是将要用到的数字放到一个连续的数组中，通过一个函数find得到数字和存放在数组中的下标的映射关系。

其中find函数的实现可以通过二分查找来实现；

练习题：
题意：

假定有一个无限长的数轴，初始时数轴的下标权威0，现在，首先进行n次操作，将位置为x的地方加上c，然后接下来有m次询问，每次询问包含两个整数l，r。我们要求的是[ l , r ] [l,r][l,r]区间里面的和

输入格式：

第一行两个数n和m；

接下来n行每行两个数x，c；

最后m次询问每行两个数l，r;

数据范围：

− 1 0 9 -10^9−10 
9
 <=x xx<=− 1 0 9 -10^9−10 
9
 

1<=n , m n,mn,m<=1 0 5 10^510 
5
 

− 1 0 9 -10^9−10 
9
 ​<=l ll<=r rr<=− 1 0 9 -10^9−10 
9
 ​

− 10000 -10000−10000<=c cc<=10000 1000010000

vector<int>all; //存放下标
int find(int x)
{int l = 0, r = all.size();while (l < r){int mid = l + r >> 1;if (all[mid] >= x)r = mid;else l = mid + 1;}return r + 1;//下标从一开始
}int main()
{// vector<vector<int>>routes = { {1,2,7} ,{3,6,7} };// numBusesToDestination(routes, 1, 6);vector<int>arr = { 200,100,300,500 };  //数字位置vector<int>arr1 = { 2,4,1,5 };         //获得的值vector<vector<int>>finds = { {1,3},{100,201},{0,1000},{300,499} };int add[100] = { 0 }; //存放数值离散后的位置vector<pair<int, int>>num;//存放数字和获得的值queue<pair<int, int>>qn;//存放查找信息int s[100] = { 0 };//存放和的数组for (int i = 0; i < arr.size(); i++){all.push_back(arr[i]);num.push_back({ arr[i],arr1[i] });}for (int i = 0; i < finds.size(); i++){all.push_back(finds[i][0]);all.push_back(finds[i][1]);qn.push({ finds[i][0],finds[i][1] });}sort(all.begin(), all.end());all.erase(unique(all.begin(), all.end()), all.end());//去重for (int i = 0; i < num.size(); i++){int x = num[i].first, c = num[i].second;add[find(x)] += c;}for (int i = 1; i <=all.size(); i++){s[i] = s[i - 1] + add[i];}while(qn.size()){auto e = qn.front();qn.pop();int l = find(e.first), r = find(e.second);cout << s[r] - s[l - 1] << endl;}}

首先将所有要用到的数存放在数组all中，并且进行去重和排序，方便后续用二分查找得到相对于的下标，然后用一个num数组，存放数字和该位置变换的大小，后续会在前缀和数组中用到，简化在l到r区间大小的计算。再用一个队列存放查找的l，r，用于后续求解。add数组存放离散化后的数字对应变化，与前面不同的是，此处是利用find联系离散前和离散后数字的下标，然后找到相应位置加上数字，再利用sum求前缀和，这样l到r区间的变化就可以用s[r]-s[l-1]来实现。find中r+1是想要从下标为1的地方开始，方便求前缀和。