第十二课-二维前缀和

为什么需要二维前缀和？

给定n*m的矩阵，如何在O(1)时间返回某个子矩阵内元素的和？二维前缀和数组可以做到！

如何O(1)时间计算子矩阵的和

先考虑特殊情况：矩阵的右上角固定为(0,0)，左下角为(endY, endX)

只需要预处理得到s(i, j)数组，表示(0,0)和(i,j)两个点形成的子矩阵元素和。

再考虑一般情况：矩阵的右上角为(startY, startX)，左下角为(endY, endX)

假设子矩阵两个点是(3,2)和(5,3)

1. 绿色区域表示的是s(5,3)
2. 想要得到红框的区域，先减去蓝色区域，蓝色区域是s(2,3)。
3. 减去黄色区域，黄色区域是s(1,5)
4. 粉色区域被减了两次，加回来。粉色区域是s(2,1)

即sum = s(5,3)-s(2,3)-s(1,5)+s(2,1)

把(3,2)和(5,3)换成(startY, startX)和(endY, endX)

sum = s(endY, endX)-s(startY-1, endX)-s(endY, startX-1)+s(startX-1,startY-1)

如何由a数组生成s数组？或者说二维前缀和如何计算？

思路

①、S(i - 1, j) 表示是坐标 (i - 1, j) 左上角所有元素和（绿色区域）。

②、S(i, j - 1) 表示是坐标 (i, j - 1) 左上角所有元素和。S(i - 1, j) + S(i, j - 1) 会导致深绿色区域重复多加1次。

③、S(i - 1, j) + S(i, j - 1) - S(i - 1, j - 1) 就是为了除去深绿色区域重复多加的1次。

④、此时还差一个坐标点 (i, j) 没有加，所以最后是 S(i - 1, j) + S(i, j - 1) - S(i - 1, j - 1) + a(i, j)。

s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)

使用递推可以生成s数组。

代码

    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];  //求前缀和。
        }
    }

参考：https://blog.csdn.net/m0_65998513/article/details/132534198

练习题

二维前缀和：

• https://www.luogu.com.cn/problem/P1387
• http://oj.oldmoon.cn/p/GESP202406