算法笔记

前面我有一篇关于蓝桥杯的博客,里面的K倍区间就是对前缀和的应用，不过那道题对前缀和做了优化,想深入了解的可以看下:蓝桥杯——2017第八届C/C++真题[省赛][B组]_skeet follower的博客-CSDN博客

首先介绍下二维矩阵的前缀和，这篇文章写的很好前缀和，这里我就拿大佬的思路来供我们参考学习.

步骤一：求 preSum
我们先从如何求出二维空间的 preSum[i][j]。

我们定义 preSum[i][j]preSum[i][j] 表示 从 [0,0][0,0] 位置到 [i,j][i,j] 位置的子矩形所有元素之和。
可以用下图帮助理解：

S(O, D) = S(O, C) + S(O, B) - S(O, A) + D

减去 S(O, A)S(O,A) 的原因是 S(O, C)S(O,C) 和 S(O, B)S(O,B) 中都有 S(O, A)S(O,A)，即加了两次 S(O, A)S(O,A)，所以需要减去一次 S(O, A)S(O,A)。

如果求 preSum[i][j]preSum[i][j] 表示的话，对应了以下的递推公式：

preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i][j]
步骤二：根据 preSum 求子矩形面积

前面已经求出了数组中从 [0,0][0,0] 位置到 [i,j][i,j] 位置的 preSum。下面要利用 preSum[i][j]preSum[i][j] 来快速求出任意子矩形的面积。

同样利用一张图来说明：

S(A, D) = S(O, D) - S(O, E) - S(O, F) + S(O, G)

加上子矩形 S(O, G)S(O,G) 面积的原因是 S(O, E)S(O,E) 和 S(O, F)S(O,F) 中都有 S(O, G)S(O,G)，即减了两次 S(O, G)S(O,G)，所以需要加上一次 S(O, G)S(O,G)。

如果要求 [row1, col1][row1,col1] 到 [row2, col2][row2,col2] 的子矩形的面积的话，用 preSum 对应了以下的递推公式：

preSum[row2][col2] - preSum[row2][col1 - 1] - preSum[row1 - 1][col2] + preSum[row1 - 1][col1 - 1]

 代码

class NumMatrix {
public:
    vector> sums;

    NumMatrix(vector>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};

 代码

#include
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],s[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    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];
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
        
    }
    return 0;
}