子矩阵的和(二维前缀和)

一、算法描述

上一篇文章介绍了一维前缀和,也就是一个数组的前n项和,这篇文章来介绍一下什么是二维前缀和。

含义

  • 一维的是前n项的和,那么二维的情况下,表示的则是与左上角形成的矩形和。

怎么求

  • 一维的递推关系式是s[i] = s[i - 1] + a[i];,我们根据含义来思考二维的递推关系式,读者可以在草稿纸上画一个矩形来更好的理解。

  • \(s[i][j]\) 表示的是 \(i, j\) 这个位置与左上角形成的矩形和,\(s[i - 1][j]\) 表示的是比 \(s[i][j]\) 少一行的矩形和, \(s[i][j - 1]\) 表示的是比 \(s[i][j]\) 少一列的矩形和。

  • \(s[i - 1][j] + s[i][j - 1]\) 得到的就是 \(s[i][j]\) ,但是少了一个 \(a[i][j]\) ,同时多了一个 \(i - 1, j - 1\) 与左上角形成的矩形和,即 \(s[i - 1][j - 1]\)

  • 综上可以得到求得 \(s[i][j]\) 的递推关系式为:s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];,读者应在草稿纸上自己推理,不要纯靠记忆。

怎么用

  • 一维前缀和的用法在 \(O(1)\) 的时间复杂度内求得 \([l, r]\) 的区间和,那么二维前缀和则是在 \(O(1)\)的时间复杂度内求得 \([x1, y1]\)\([x2, y2]\)这个区域的矩形和。

  • 显然我们要用 \(s[i][j]\) 这块大面积来减去其他的面积,那么需要减去哪些部分呢?大家自行在草稿纸上推演,计算如下:s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];,根据含义来思考如何推算。

二、题目描述

输入一个 \(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 

三、题目来源

AcWing算法基础课-796.子矩阵的和

四、源代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
        
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
            
    while (q -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
    
    return 0;
}

热门相关:重生之将门毒后   上将大叔,狼来了!   重生之女将星   悠哉兽世:种种田,生生崽   魔神狂后