前缀和算法 | 计算分矩阵的和
文章目录
- 一维前缀和
- 预处理
- 二维前缀和
- 预处理
- 运用 和数组 计算指定子矩阵
- 常规情况
- 边界情况
一维前缀和
预处理
需要一个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];
常规情况
白色的框表示 数据区域 可能不是很清楚