网站建设应用,品牌建设需要哪几层工作,软件开发工程师薪资水平,一般做个网站多少钱文章目录 #x1f34e;1. 题目#x1f352;2. 算法原理#x1f345;3. 代码实现 #x1f34e;1. 题目 题目链接#xff1a;【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 描述
给你一个 n 行 m 列的矩阵 A #xff0c;下标从1开始。
接下来有 q 次查询#xff0… 文章目录 1. 题目2. 算法原理3. 代码实现 1. 题目 题目链接【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 描述
给你一个 n 行 m 列的矩阵 A 下标从1开始。
接下来有 q 次查询每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和
输入描述
第一行包含三个整数n,m,q.
接下来n行每行m个整数代表矩阵的元素
接下来q行每行4个整数x1, y1, x2, y2分别代表这次查询的参数
1 ≤ n ≤ 1000 1 ≤ q ≤ 105 -109 ≤ a[i] [j] ≤ 109 1 ≤ x1 ≤ x2 ≤ n 1 ≤ y1 ≤ y2 ≤ m
输出描述
输出q行每行表示查询结果。
示例1
输入
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4输出
8
25
32备注
读入数据可能很大请注意读写时间。这题就是一个升级版的前缀和——DP34 【模板】前缀和将一维数组升级成了二维数组 2. 算法原理
解法一暴力模拟
这里照样直接模拟要哪个区间到哪个区间我们直接遍历加上这里时间复杂度为O(nmq)
解法二前缀和
采用前缀和方法分为2步 预处理出来一个前缀和矩阵dp[i][j]表示从[1,1]位置到[i,j]位置 如果我们求dp[i][j]的时候依旧从前往后依次遍历那这个时间复杂度也是蛮高的我们可以将要求的dp[i][j]抽象成4个部分 那么则有dp[i][j] A B C D其中A和D好求B区域可以理解为(AB)-AC也同理(AC)-A这样就能推出dp[i][j] (AB)(AC)D-A 所以dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1]这样之后我们就可以直接从dp表里面拿值了这个时间复杂度为O(1) 使用前缀和矩阵假设我们求得区域为[x1y1] ~ [x2y2] 我们要求的就是D区域但是dp表里面没有D区域的直接值但D (ABCD) - (AB) - (AC) A表里面有A、AB和AC的值所以D dp[x2][y2] -dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]得出这个公式那我们每次使用这个前缀和矩阵的时候时间复杂度也是O(1)。
那么整体的时间复杂度为O(mn)O(q)
3. 代码实现
#include iostream
#includevector
using namespace std;int main()
{int n 0,m 0,q 0;cinnmq;vectorvectorint arr(n1,vectorint(m1));for(int i1;in;i)for(int j1;jm;j)cinarr[i][j];//预处理前缀和矩阵vectorvectorlong long dp(n1,vectorlong long(m1));for(int i1;in;i)for(int j1;jm;j)dp[i][j]dp[i-1][j]dp[i][j-1]arr[i][j]-dp[i-1][j-1];//使用前缀和矩阵int x1 0,x2 0,y1 0, y2 0;while(q--){cinx1y1x2y2; //输入顺序coutdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]endl;}return 0 ;
}
