题目

https://www.acwing.com/problem/content/798/

算法思想

这是前缀和问题的二维矩阵版本，在读取数据的时候，每个点代表下图所示范围内的和：

公式如下：

arr[x][y] = arr[x-1][y] + arr[x][y-1] - arr[x-1][y+1];

本题目给出两个点，要求计算出两个对角点之间的总和

公式如下：

arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1];

题解

#include <iostream>

const int N = 1010;
int arr[N][N];

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

复杂度

时间复杂度：O(1)，空间复杂度：O(1)