算法之前缀和和差分

一.前缀和

首先我们来看下面这道题：

假如给你一个数组从a1到an，接下来有m次询问,每次询问有两个参数l,r，请问al到ar之和，每次询问按行输出？？？

对于这个问题，如果你是没有这方面基础的，第一反应肯定是我们对于每个询问直接暴力遍历al到ar区间，输出结果，时间复杂度为O(N^m)，但是如果我对于你的时间复杂度限制到O(N)，你的操作肯定就会超时，所以接下来你该如何操作呢？

经过仔细思考的你，发现如果你们对每个位置i，统计其前面所有下标的和（包括其位置），此时如果你用ar-a(l-1)就可以在O(1)的时间应对每次询问，时间复杂度就优化到了O(n)

下面我们简单的实现其代码：

#include <bits/stdc++.h> 
using namespace std;
const int N =1e5;
int n,l,r,m;
int a[N+1];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	//前缀和处理：
	for(int i=1;i<=n;i++) 
	{
		a[i]=a[i-1]+a[i];//初学可以用dp[i]=dp[i-1]+a[i] 
	}
	while(m--)
	{
		cin>>l>>r;
		cout<<a[r]-a[l-1]<<"\n";
	}
	return 0;
}

我们现在知道了前缀和算法，那么我们什么时候会使用该算法呢？？？

对于一个算法学习这是非常重要的内容，对于一个算法的掌握唯有知道什么时候用再加上多练习使用，才能在比赛中想到使用！！！

对于该前缀和算法，我们发现如果我们想要一个数组内部从某个位置到某个位置的某种关系时，就可以使用该算法

下面我们来学习另一种算法：

二.差分：

我们长话短说，还是从一道题目看起：

现在有一个数组从a1到an，接下来有m次操作，每次操作输入两个数l,r，将al到ar区间每个数-1，现在m次操作后输出该数组？？？

对于该题，第一反应如果你是想到了前缀和，那么恭喜你，肯定是将前面的内容仔细阅读过的，但是现在问题是，我们直接用前缀和是无法解决该问题的，因为我们要的是整个数组，仔细思考之后，你有回到了暴力，想如果我们对于每次询问将l和r区间的内容都减少-1,时间复杂度为O(N*N)

如果还是对你作出限制，时间复杂度要求为O(N*m)，请问阁下又该如何应对？？？

如果此时你不感到烦躁，可以试试思考下，毕竟如果你在没学过的情况下就能想到接下来的做法，我只能说声：大哥，苟富贵，莫相忘！！！

好了，回到正题！

如果我们对于al到ar区间都-1,等价于对于al到an区间都-1，然后再对a(r+1)区间+1，此时就满足题目要求，接下来我们如果用一个相同大小的数组，将bl位置-1,b(r+1)位置+1，此时如果你回想一下，如果再对b数组一次前缀和：如下操作：

定义一个dp数组：

dp[i]=dp[i-1]+b[i](注意边界处理，最好从一开始）

此时我们是不是就相当于进行了题目要求的操作，如果我们直接现在b数组上进行m次操作，在前缀和遍历一遍，是不是就可以输出该数组的结果，时间复杂度为O(N*m)

代码如下：

#include <bits/stdc++.h> 
using namespace std;
const int N =1e5;
int n,l,r,m;
int a[N+1],b[N+1],dp[N+1]; 
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(m--) 
	{
		cin>>l>>r;
		b[l]++;b[r+1]--;
	}
	//注意：dp[i]表示为前i个b数组中元素处理后结果，包括i位置
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1]+b[i];
	}
	for(int i=1;i<=n;i++) 
	{
		a[i]+=dp[i];
	}
	//输出; 
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	return 0;	
}

此时同样我们还是来思考下该算法的使用范围，是不是如果我们想要对数组中一段区间范围同时进行相同操作，并且重复多次该操作，然后问数组相关的解答时，该算法是非常合适的，没错，这就是该算法的使用情景。

今天我们学习了前缀和和差分，希望大家好好掌握！！！