前缀和&差分

一维前缀和

• 前缀和即为数组的前n项和
• presum[i]=a[1]+a[2]+...+a[i]
• 区间查询
  • 求$[l,r]$的区间和为：presum[r]-presum[l-1]

for(int i=1;i<=n;i++) 
	presum[i]=a[i]+presum[i-1];

二维前缀和

• s[i][j]表示二维数组中，左上角(1,1)到右下角(i,j)所包围的矩阵元素的和
• 预处理

for(int i=1;i<=n;i++) {
	for(int j=1;j<=m;j++) {
		s[i][j] = s[i][j-1]+s[i-1][j]+a[i][j]-s[i-1][j-1];
	}
}

• 区间查询
  • 查询以(x1,y1)为左上角，(x2,y2)为右下角的矩形元素之和

int sum = s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];

差分

• 差分是前缀和的逆运算。
• 差分数组b[i]=a[i]-a[i-1],b[0]=a[0]

for(int i=1;i<=n;i++) {
	b[i]=a[i]-a[i-1];
}

• 对差分数组求前缀和即可还原数组
• 区间更新
  • 对a数组区间$[l,r]$的数都加上$c$

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

• 将更新封装成一个函数

void insert(int l,int r,int c) {
	b[l]+=c;
	b[r+1]-=c;
}

• 构建差分数组则为

for(int i=1;i<=n;i++) {
	insert(i,i,a[i]);
}

二维差分

• 构造二维差分数组目的是为了 让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，可以由O(n*n)的时间复杂度优化成O(1)
• 区间更新,对a[x1,y1]~a[x2,y2]的矩形区域加上c

void insert(int x1,int y1,int x2,int y2,int c) {
	b[x1][y1]+=c;
	b[x2+1][y1]-=c;
	b[x1][y2+1]-=c;
	b[x2+1][y2+1]+=c;
}

• 构造二位差分

for(int i=1;i<=n;i++) {
	for(int j=1;j<=m;j++) {
		insert(i,j,i,j,a[i][j]);
	}
}