关于一维差分数组的例子
2020-11-14
·
hexer

有n个数,m个操作,每一次操作,将x~y区间的所有数增加z 代码如下:

#include<stdio.h>
int a[100000],b[100000];
//a是原本的数组,b是差分数组 
int main()
{
	int x,y,z;
	int n,m;
	int sum=0;
	scanf("%d %d",&n,&m);
	for(int i=1 ; i<=n ; i++)
	{
		scanf("%d",&a[i]);//a[0]是0 
		b[i]=a[i]-a[i-1];//差分数组 
	}
	for(int i=1 ; i<=m ; i++)//m组修改 
	{
		scanf("%d %d %d",&x,&y,&z);//x到y的区间,增加z 
		b[x]+=z;
		b[y+1]-=z;//记住+1
	}
	for(int i=1 ; i<=n ; i++)
	{
		sum+=b[i];//累加 
		printf("%d ",sum);
	}
}

样例: 5 1 1 2 3 4 5 1 5 9 输出: 10 11 12 13 14