优选算法_前缀和_二维前缀(模板)_C++

一.题目分析

这里题目不好理解,就是一个指定大小的矩阵(n行m列),然后再给出两个坐标,之后求两坐标所围成矩阵的和

1.暴力解法->模拟:询问一次就求一次和,所以时间复杂度是q*m*n

2.前缀和

        1.预处理一个前缀和矩阵

我们发现抽出的BC的面积并不好求,所以我们就求好求的面积减去多余面积即可

        2.使用前缀和矩阵

二.代码实现

#include<iostream> #include<vector> int mian() { //1.读入数据 int n, m,q; cin >> n >> m >> q; vector<vector<int>>arr(n + 1, vector<int>(m + 1)); for (int i = 1;i <= n;i++) for (int j = 1;j = m;j++) cin >> arr[i][j]; //2.预处理前缀和矩阵 vector<vector<long long>>dp(n + 1, vector<long long>(m + 1)); for (int i = 1;i <= n;i++) for (int j = 1;j = m;j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]; //3.使用前缀和矩阵 int q; cin >> q; while (q) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout<< dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1][y1]; } return 0; }

ps:我们矩阵是从(1,1)开始的因为会有越界的情况,相加就是dp[0][0]=0;相乘就是dp[0][0]=1;需要考虑边界情况;