AcWing 796. 子矩阵的和【二维前缀和 c++详细题解】

- 日理万妓 2021-09-03 03:46 420阅读 0赞

# 二维前缀和 #

--------------------

## 题目 ##

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

**输入格式**  
第一行包含三个整数n，m，q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

**输出格式**  
共q行，每行输出一个询问的结果。

**数据范围**  
1≤n,m≤1000,  
1≤q≤200000,  
1≤x1≤x2≤n,  
1≤y1≤y2≤m,  
−1000≤矩阵内元素的值≤1000  
**输入样例：**  
3 4 3  
1 7 2 4  
3 6 2 8  
2 1 2 3  
1 1 2 2  
2 1 3 4  
1 3 3 4  
**输出样例：**  
17  
27  
21

## 二维前缀和推导 ##

**如图：**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

**紫色面积**是指`(1,1)`左上角到`(i,j-1)`右下角的矩形面积, **绿色面积**是指`(1,1)`左上角到`(i-1, j )`右下角的矩形面积。**每一个颜色的矩形面积都代表了它所包围元素的和。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
**从图中我们很容易看出**，整个外围蓝色矩形面积`s[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 ] + a[i] [j] - s[i-1][ j-1]`

**接下来回归问题**去求以`(x1,y1)`为左上角和以`(x2,y2)`为右下角的矩阵的元素的和。

**如图：**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2][]

**紫色面积**是指 `( 1,1 )`左上角到`(x1-1,y2)`右下角的矩形面积 ，**黄色面积**是指`(1,1)`左上角到`(x2,y1-1)`右下角的矩形面积；

**不难推出：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]

绿色矩形的面积 = 整个外围面积`s[x2, y2]` \- 黄色面积`s[x2, y1 - 1]` \- 紫色面积`s[x1 - 1, y2]` \+ 重复减去的红色面积 `s[x1 - 1, y1 - 1]`

**因此二维前缀和的结论为：**

以`(x1, y1)`为左上角，`(x2, y2)`为右下角的子矩阵的和为：  
`s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]`

**总结：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4][]

### [前缀和与差分的个人心得总结][Link 1] ###

**代码：**

#include<iostream>
    #include<cstdio>
    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]+a[i][j]-s[i-1][j-1];  //求前缀和
            }
        }
        while(q--)
        { 
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/76da8d3169504ba9b8a7e068bdf2c687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/1af945eba0e14606b967b14c952a6698.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/6287b2d914744370970f9698c619c432.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/4f3f484401a44fe7b3d9466dc84a7312.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]: /images/20210724/b377ed0059e24dc5af5ec1f69bb820e7.png
[Link 1]: https://blog.csdn.net/weixin_45629285/article/details/111146240