子矩阵求和 代码

#include<iostream>
using namespace std;

constexpr int N = 1e+3 + 10;
int a[N][N], s[N][N];
int n , m, q;

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-1][j] + s[i][j-1] - 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;
}

要点 –》 主要是对公式的理解(理解其推导的过程)

. 这里主要有两个公式

1. S[i][j] 数组各项的求值

1. 区间的计算