差分（前缀和的逆运算）

⬅ 返回

1、一维差分（数组）

题目

step1：构造差分数组，s[]为原数组（前缀和数组）， a[]为差分数组

for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		a[i]=s[i]-s[i-1];//差分
	}

step2：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。

a[l]+=c;
a[r+1]-=c;

step3：结果

for(int i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i];//一维前缀和
		cout<<s[i]<<" ";
	}

时间复杂度为O(1), 大大提高了效率。

1、二维差分（矩阵）

题目

step1：构造差分数组a[]，s[]为原数组（前缀和数组）， a[]为差分数组

for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
			a[i][j]=s[i][j]+s[i-1][j-1]-s[i-1][j]-s[i][j-1];//差分 二位前缀和的逆用
		}
	}

step2：

		a[x1][y1]+=c;
		a[x2+1][y1]-=c;
		a[x1][y2+1]-=c;
		a[x2+1][y2+1]+=c;

step3：结果

for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				
				s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//二维前缀和
				cout<<s[i][j]<<" ";
			}
			cout<<endl;
		}