前缀和算法 | 计算分矩阵的和

一维前缀和

预处理

需要一个sum数组(和输入数组一样长) 从序号一 开始累加，得到每个序号对应的和的值。
Sum[i]=Sum[i−1]+A[i−1]

• Sum[i-1]：表示从数组开始到第 i-2 个元素的和。
• A[i-1]：表示当前元素的值。

有点类似与概率论里的分布函数（单调不减）的概念。
F(x) = P(X<=x) 从-∞ 累加到x。
若要求某一区间内的值
如P( 2 < x <= 4) = F(4) - F(2)

二维前缀和

纵i 横j

预处理

由图可知，sum可以分为四个小块，于是我们得到下面公式
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];

就这么简单吗？不，我在实现过程中发现：还需要考虑边界问题(数组越界)，

在**第一行(i=0)或者第一列(j=0)**处理时，带入公式，显然越界. s[-1][-1]!!!
于是我们需要单独处理第一行和第一列。

代码如下 其中n对应数据数组的行数 m对应数据数组的列数

	// 初始化第一行
	for (int j = 0; j < n; ++j) {
		sum[0][j] = (j > 0 ? sum[0][j - 1] : 0) + a[0][j];
	}

	// 初始化第一列
	for (int i = 0; i < m; ++i) {
		sum[i][0] = (i > 0 ? sum[i - 1][0] : 0) + a[i][0];
	}
	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
		{
			sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

运用 和数组 计算指定子矩阵

同样需要考律边界的问题
其中

• i, j表示子矩阵的右下角的点的坐标，
• net_h表示子矩阵在 i轴(行)方向的高度
• net_w表示子矩阵在 j轴(列)方向的宽度

如果子矩阵挨着i轴，j轴，计算时必定出界

	if (i + 1 == net_h && j + 1 == net_w)  //边界条件
		total = sum[i][j];
	else if (i + 1 == net_h)         //如果子矩阵挨着i轴，j轴，计算时必定出界
		total = sum[i][j] - sum[i][j - net_w];
	else if (j + 1 == net_w)
		total = sum[i][j] - sum[i - net_h][j];
	else
		total = sum[i][j] - sum[i - net_h][j] - sum[i][j - net_w] + sum[i - net_h][j - net_w];

常规情况

白色的框表示 数据区域 可能不是很清楚

边界情况