差分及简单运用

所谓差分，即是将数列中的每一项与前一项作差。

例如 1 8 9 3 6 5，差分后即得 1 7 1 -6 3 -1

差分后的第一个数与原数列的第一个数相同，即相当于第一项减0

差分后的数列前n项的和即为原数列第n项的值。

应用

在某数列的 [  L  ,  R  ] 区间上的每个数加上某个值（这里假设加1），即只需要在差分数列的 L 处+1，R+1 处-1即可。

如此可将原时间复杂度为O(n)的操作简化为仅有O(1)时间复杂度的操作。

例题

 代码如下

#include 
int arr[1010][1010]={0};
int main(void)
{
	int n,m,i,j,l,x1,x2,y1,y2;
	scanf("%d%d",&n,&m);
	for(i=0;i