前缀和与差分

前缀和

一维前缀和

s[i]代表前i个数的和

S[i] = a[1] + a[2] + ... a[i] //前缀和初始化,边界s[0]=0
a[l] + ... + a[r] = S[r] - S[l - 1] //求区间[l,r]的和，O(1)时间

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

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

for (i = 1; i <= n; i++){
	for (j = 1; j <= n; j++){
		s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
	}
}//初始化

差分

一维差分

初始化

b[0] = a[0]
b[i] = a[i] - a[i-1] i>0

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

我的理解，就是[l,]区间的数加上了c,[r+1]区间的数减了c,最后就是[l,r]加上了c,这样更好理解二维差分

public void insert(int[] b, int l, int r, int c){
	b[l]+=c;
	b[r+1]-=c;
}//[l,r]区间每个数加c

for (int i = 1; i<=n ;i++){
	insert(b, i, i, a[i]);
}//初始化差分数组b，注意b数组大小至少为n+2;

for (int i = 1; i <= n; i++){
	b[i]+=b[i-1];
}//差分数组转化为原来的数组

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

S[x1, y1] += c表示给(x1,y1)右下角矩阵所有元素加上c

public void insert(int[] b, 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][y2]+=c;
}

| | | |
| | | |
| | | |
| | | |
for (int i = 1; i <= n; i++){
	for (int j = 1; j <= m; j++){
		insert(b,i,j,i,j,a[i][j])
	}
}//初始化

for (int i = 1; i <= n; i++){
	for (int j = 1; j <= m; j++){
		b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1];
	}
}//使用前缀和使差分数组变为前缀和数组