前缀和--二维矩阵的前缀和

这篇具有很好参考价值的文章主要介绍了前缀和--二维矩阵的前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


原题链接

子矩阵的和

输入一个 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
输入样例:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例:
17
27
21

思路:

前缀和--二维矩阵的前缀和,acwing算法基础,矩阵,线性代数
前缀和--二维矩阵的前缀和,acwing算法基础,矩阵,线性代数
我们计算的是s[i][j] 即表示第一张图内所有数字的总和
动态规划怎么利用上之前已经有的值
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]
题目中要求计算 x1,y1,x2,y2范围内的总和
可以用
s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

此题画图后便一目了然文章来源地址https://www.toymoban.com/news/detail-793185.html

代码:

#include <iostream>

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

int main() {
    int n, m, q;
    cin >> 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][j - 1] + s[i - 1][j] - 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;
}

到了这里,关于前缀和--二维矩阵的前缀和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图解AI数学基础 | 线性代数与矩阵论

    一个标量就是一个单独的数。 只具有数值大小,没有方向 (部分有正负之分),运算遵循一般的代数法则。 一般用小写的变量名称表示。 质量mmm、速率vvv、时间ttt、电阻ρrhoρ 等物理量,都是数据标量。 向量指具有大小和方向的量,形态上看就是一列数。 通常赋予向量

    2024年04月10日
    浏览(48)
  • 线性代数(基础篇):第一章:行列式 、第二章:矩阵

    1. A可逆 ⇦⇨①|A|≠0 ⇦⇨②r(A)=n,A满秩 ⇦⇨③A的列向量 α₁,α₂,…α n 线性无关 ⇦⇨④Ax=0仅有零解 (系数矩阵的秩 = 列数,列满秩) ⇦⇨⑤ A的特征值均不为0 【17年5.】 2.  A不可逆 ⇦⇨①|A|=0 ⇦⇨②r(A)n,A不满秩 ⇦⇨③A的列向量 α₁,α₂,…α n 线性相关 ⇦⇨④Ax=0有非

    2024年02月16日
    浏览(50)
  • 线性代数的学习和整理1:用EXCEL进行基础的矩阵计算

    目录 1 写在最开始的话 EXCEL里计算线性代数的起点 心得 内容 2 EXCEL里矩形的加法 2.1  矩阵加法的性质 3 EXCEL里矩阵的减法 4 矩阵标量乘法/ 也称 数乘 4.1 矩阵的标量乘法的性质 5 矩阵点乘, 得到:点积/内积 ,使用mmult() 5.1 矩阵点乘规则 5.2  矩阵的乘法不符合交换性,不能交

    2024年03月20日
    浏览(49)
  • 线性代数 --- 计算斐波那契数列第n项的快速算法(矩阵的n次幂)

    The n-th term of Fibonacci Numbers:         斐波那契数列的是一个古老而又经典的数学数列,距今已经有800多年了。关于斐波那契数列的计算方法不难,只是当我们希望快速求出其数列中的第100,乃至第1000项时,有没有又准又快的方法,一直是一个值得探讨和研究的问题。笔者

    2024年04月27日
    浏览(44)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • 前缀和例题:子矩阵的和AcWing796-Java版

    //前缀和模板提,在读入数据的时候就可以先算好前缀和的大小 // 计算前缀的时候用 :g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]); // 计算结果的时候用 :g[x2][y2] - g[x1 - 1][y2]- g[x2][y1-1]   + g[x1 -1][y1 - 1] + \\\"n\\\" //一些重复加的地方都需要减掉,如计算前缀和的时候 g[i-1

    2024年02月02日
    浏览(41)
  • 前缀和--二维矩阵的前缀和

    原题链接 输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2 ,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n,m,q 。 接下来 n 行,每行包含 m 个整数,表示整数矩阵。

    2024年01月16日
    浏览(40)
  • 【Paddle】PCA线性代数基础 + 领域应用:人脸识别算法(1.1w字超详细:附公式、代码)

    🌈你好呀!我是 是Yu欸 🌌 2024每日百字篆刻时光,感谢你的陪伴与支持 ~ 🚀 欢迎一起踏上探险之旅,挖掘无限可能,共同成长! 主成分分析(PCA,Principal Component Analysis)是一项在高维数据中,寻找最重要特征的降维技术,大大减少数据的维度,而不显著损失信息量。 本文

    2024年04月28日
    浏览(47)
  • 利用前缀和计算二维矩阵子矩阵的和

    作者简介 :一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。 座右铭 :未来是不可确定的,慢慢来是最快的。 个人主页 :极客李华-CSDN博客 合作方式 :私聊+ 这个专栏内容 :用最低价格鼓励和博主一起在寒假打卡高频大厂算法题,

    2024年04月17日
    浏览(44)
  • 子矩阵的和(二维前缀和)

    上一篇文章介绍了一维前缀和,也就是一个数组的前 n 项和,这篇文章来介绍一下什么是二维前缀和。 含义 一维的是前 n 项的和,那么二维的情况下,表示的则是与左上角形成的矩形和。 怎么求 一维的递推关系式是 s[i] = s[i - 1] + a[i]; ,我们根据含义来思考二维的递推关系

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包