SolitudeAlma

今天我们来讲一下二位前缀和

什么叫二位前缀和呢？

给我们一个 $n \times m$ 的矩阵，矩阵中任意一点的左上角的点的数之和加上这个点的值为该点的二维前缀和 $s[i][j]=\sum_{i=1...i}^{j=1...j} a[i][j]$ 。

那么我们应该怎么用公式求呢？

首先我们用s数组来表示前缀和，那么 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i- 1][j - 1] + a[i][j] ，即这一个点的二位前缀和等于它左边的点和上面的点的前缀和之和减去左上角的点的前缀和（即多加的部分）再加上这个点的值就是该点的二维前缀和，其实就是容斥定理。可以结合下图理解。

橙色部分是左边的点的前缀和，红色部分是上面的点的前缀和，绿色的点是重复部分，褐色是当前的点

既然我们求出了每一个点对应的二维前缀和，那么如果需要求子矩阵的二维前缀和呢，该怎么求。

其实也很简单，从定义出发，以（x1，y1）为左上角，（x2，y2）为右上角的子矩阵的前缀和可以看成是（x2，y2）的前缀和减去（x2，y1-1）的前缀和再减去（x1-1，y2）的前缀和最后再加上（x1-1，y1-1）的前缀和即可。用公式表示就是 s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] 。可以结合下图理解。

红色部分为所求区域，绿色和橙色是多余部分要减去，而灰色部分是多减了要加回来。

到这里相信你也懂得了怎么求矩阵的二维前缀和，那么我们直接上模板吧


S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

接着我们来做一道模板题

AcWing 796.子矩阵的和

题目描述

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

输入样例：

输出样例：

17
27
21

C++代码

#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]) , 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[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}

引用

引用一下大佬的题解

Bug_FreeOωO AcWing 796. 子矩阵的和

zning AcWing 796. 子矩阵的和_Java

二位前缀和