Acwing 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

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

讲解：

首先明确一下题意，先输入两个整数n、m，n代表在区间[-1e9,1e9]某一点加一个整数的次数，输入x c在x处加上c，m代表求某个区间和的次数，输入l r求区间[l,r]的和。 

所以此处略作分析，为什么要离散化呢，因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，第二个原因，本文是数轴，要是采用下标的话，可能存在负值，所以也不能，所以有人可能会提出用哈希表，哈希表可以吗？答案也是不可以的，因为哈希表不能像离散化那样缩小数组的空间，导致我们可能需要从-e9遍历到1e9（此处的含义就是假如我们需要计算1e-9和1e9区间内的值，那我们需要从前到后枚举，无论该值是否存在），因为哈希表不能排序，所以我们一般不能提前知道哪些数轴上的点存在哪些不存在，所以一般是从负的最小值到正的最大值都枚举一遍，时间负责度太高，于是就有了本题的离散化，离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

其实映射最大的难点是前后的映射关系，如何能够将不连续的点映射到连续的数组的下标。此处的解决办法就是开辟额外的数组存放原来的数组下标，或者说下标标志，本文是原来上的数轴上的非连续点的横坐标。
此处的做法是是对原来的数轴下标进行排序，再去重，为什么要去重呢，因为本题提前考虑了前缀和的思想，其实很简单，就是我们需要求出的区间内的和的两端断点不一定有元素，提前加如需要求前缀和的两个端点，有利于我们进行二分搜索，其实二分搜索里面我们一般假定有解的，如果没解的话需要特判，所以提前加入了这些元素，从而导致可能出现重复元素。

所以我们将解题步骤主要分为以下五步：

第一首先读入，将每次读入的x c push_back()到add中，将每次读入的位置x push_back()到alls中，将每次读入的l r push_back()到zon中。之后我们对其进行排序去重。去重之后我们进行遍历add，然后在离散化的数组映射到的a数组中进行加上c的操作（用到find函数），后需要初始化s数组，最后我们再次遍历ton，完成求区间[l,r]就可以了。

所以我们这个题最主要的其实就是我们要将之前的点通过映射，映射至一个全新的数轴上，使其在这个全新的数轴上进行一个新的运算。

AC：

#include
#include
#include 
 
using namespace std ;
 
typedef pair<int, int> PII ;
 
const int N = 300010 ;
 
int n, m ;
int a[N], s[N] ;
 
vector<int> alls ;
vector add, zon ;
 
int find(int x)
{
	int l=0, r=alls.size()-1 ;
	
	while(l
	{
		int mid = (l+r) >> 1 ;
		if(alls[mid] >= x)	r=mid ;
		else	l=mid+1 ;
	}
	
	return r+1 ;
	
}
 
 
int main()
{
	cin >> n >> m ;
	
	for(int i=0; i
	{
		int x, c ;
		cin >> x >> c ;
		
		alls.push_back(x) ;
		add.push_back({x,c}) ;
	}
	
	for(int i=0; i
	{
		int l, r ;
		cin >> l >> r ;
		
		alls.push_back(l) ;
		alls.push_back(r) ;
		
		zon.push_back({l,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:zon)
	{
		int l = find(item.first), r = find(item.second) ;
		cout << s[r] - s[l-1] <
	}
	return 0 ;
	
}

结果：