差分和一维前缀和

一维前缀和

​ 说道一维前缀和，我们可以理解为——一个数列求前 n 项和。没错，一维前缀和就是这么简单，就是一个求前 n 项和的思想。

$$S[i]=\sum_{j=1}^iA[j]$$

for(int j=1;j<=i;j++)
{
    cin>>a[j];		//scanf("%d",&a[j]);
    s[j]=s[j-1]+a[j];//其中s[j]表示前j项和，a[j]表示第j项数
}

如果我们要求一个数列中某个区间的和，我们就可以用到前缀和的思想。例如求 $[l,r]$ 这个区间中数的和：

$$sum[l,r]=\sum_{i=l}^rA[i]=S[r]-S[l-1]$$

所以想要求这个区间中数字的和，我们只需要用前 r 项和减前 l-1 项和。

cin>>l>>r;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}
cout<<s[r]-s[l-1]<<endl;

差分

说道一维前缀和，差分这个思想也就不得不提一下了，差分数组就是一个表示当前数和前一项数的差值所构成的数组，直接上图解释：

其实在以前我们应该或多或少的遇到过这用法，例如：求一组数据的平局值，但是因为数据太大，而且不能用计算器之类的东西来辅助我们计算，我们只能口算，因此我们会将这一堆数字（ n 个）做一个处理：找到一个出现次数尽量多的数 A ，然后每个数都用其与 A 的差值来代替，然后直接 n * A +（这些处理之后的数字之和）。如此思想就和差分的思想差不多了。

差分数组和前缀和的应用

我们假设 a 数组表示原始的数组， d 数组表示差分数组， sum 数组表示前缀和数组， f 为探究用的中间数组，那么我们可以将这几个数组表示为：

d[i]=a[i]-a[i-1]（1<= i <=n , a[0]=0 , d[1]=a[1] ）;

f[i]=f[i-1]+d[i] （1<= i <=n , f[1]=d[1]=a[1] ）;

sum[i]=sum[i-1]+a[i] （1<= i <=n , sum[1]=f[1]=d[1]=a[1] ）;

由此，我们可以从第一项开始推：

所以，可以得出结论，其实 f 数组就是 a 数组。到此差分数组 d 、前缀和数组 sum 、原数组 a 的关系就差不多理清了，但是要想掌握这个只是我们还需要实际的应用。

例1：Imperishable Night

这道题就是标准的差分思想的题目，但是要注意这输入的数据比较大，如果用cin、cout要关闭同步流。

#include<stdio.h>
int n,q,l,r,k;
int d[1000000+50];//差分数组
int a[1000000+50];//表示答案的数组
/*
用到了差分思想：改变一个区间的值，但是这个区间之内的数的差距并没有变化，因此只需要盖面这个区间的端点的值就行了。最后再根据差分数组和原数组的关系，来得出原数组就行了(也就是答案数组)。
*/
int main()
{
    scanf("%d%d",&n,&q);
    while(q--)
    {
        scanf("%d%d%d",&l,&r,&k);
        d[l]+=k;
        d[r+1]-=k;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+d[i];
        if(i==1)printf("%d",a[i]);
        else printf(" %d",a[i]);
    }
    printf("\n");
    return 0;
}

例2：

有 n 个数。 m 次操作,每一次操作，将 l ~ r 区间的所有数增加 k ;最后有 q 次询问，每一次询问求出 l ~ r 区间的和。

思路：因为要将一个区间的所有数都加 k ，如果用遍历操作来实现的话时间复杂度大大提高，因此，我们可以用差分来实现，这个就和上面那道题一样，然后因为要求一个区间的和，这就是前缀和的裸题，这个也好做，只要注意处理的操作，而且，因为这道题是拿来练手的，所以还没有卡时间，卡空间之类的，只需要掌握到差分和前缀和的应用就行了。

#include<stdio.h>
int n,m,q,l,r,k;
int a[10000],d[10000],f[10000],sum[10000];
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		d[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&l,&r,&k);
		d[l]+=k;
		d[r+1]-=k;
	}		
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1]+d[i];
		sum[i]=sum[i-1]+f[i];
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",sum[r]-sum[l-1]);
	}
}