二维前缀和与差分_二维前缀和差分

回顾一下 一维前缀和

前缀和数组中 每个元素s[i]的含义都是 从原数组的第一个数a[1]到第i个数a[i]的和

类比一下 二维前缀和

前缀和数组中 每个元素s[i][j]的含义应该是什么？

思考一下再往下划

答案

从坐标(1,1)到坐标(i,j)的矩阵中全部元素的和

//仍然节省特判，所以整个第0行第0列全部空出来(值为0)

---

那么已知一维前缀和的作用是

求一个数组[l,r]区间的所有元素的和

类比 二维前缀和 其作用应该是

求一个二维数组 从 坐标(x1,y1) 到 坐标(x2,y2) 的矩阵中所有元素之和

注意：我们人为规定 x2 >= x1 , y2 >= y1 ，也就是两个坐标点分别是矩阵左上角和右下角

如果使用双重for循环加和 单次查询时间复杂度为O（（x1-x2） * （y1-y2）)

前缀和之后 单次查询时间复杂度降为O(1)

---

已知 原数组

a[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1];

那么如何构建这样的二维前缀和数组

公式为 s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

void get_prefixSum_Array(int a[], int s[], int n, int m){
	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];
		}
	}
}

那么如何求得 (x1,y1) 到 (x2,y2) 的矩阵元素和呢

公式为 sum = s[x2][y2] + s[x1-1][y1-1] - s[x1-1][y2] - s[x2][y1-1];

那么二维差分同样

咱们回顾一维差分 作用是

对一个数组的[l,r]区间全部元素做相同的改动(例如全部 + c)

那么二维差分的作用是

对一个二维数组的 坐标(x1,y1) 到 坐标(x2,y2)的矩阵中全部元素+c

已知 差分 是 前缀和 的逆运算

对于二维差分也是如此

二维前缀和数组构建公式为

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

则二维差分数组构建公式为

b[i][j] = a[i-1][j-1] + a[i][j] - a[i-1][j] - a[i][j-1];

差分数组构建完毕后

每次做改动

所用到的公式为

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

tips:

二维前缀和与差分的思想更加抽象，公式的推导不再像一维那么简单和意义明了，如果对于公式不太理解可以试试画图，像是四个小矩阵的互相遮盖、拼凑，最后得到所需要的矩阵元素和

总结：

把二维数组想象为从0开始 有下(x)右(y)两个正方向，x方向以n结束，y方向以m结束的平面直角坐标系

二维前缀和数组是从当前下标开始，左上方所有元素的和

对二维差分数组做的改动影响的实际是右下方的所有元素