796.子矩阵的和(acwing)

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

796.子矩阵的和

题目描述

输入一个 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

前缀和

#include <bits/stdc++.h> // 包含大部分标准库
using namespace std;

const int z = 1010; // 设置数组的最大长度,因为数据范围是1≤n,m≤1000
int a[z][z], s[z][z]; // a是原始的矩阵,s是用来存储前缀和的矩阵

int main()
{
    int n, m, q; // n是行数,m是列数,q是查询次数
    scanf("%d %d %d", &n, &m, &q); // 读入n, m, q
    for (int i = 1; i <= n; i++) // 从1开始,因为前缀和需要从(1,1)开始计算
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][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; // 查询的子矩阵的左上角和右下角坐标
        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;
}

这段代码的核心思想是二维前缀和。二维前缀和是一种数据预处理技术,它使得我们能够快速(在常数时间内)查询任何子矩阵的元素和。二维前缀和 s[i][j] 表示原始矩阵中所有位于第1行第1列到第i行第j列形成的子矩阵的元素之和。

这样,如果我们想要计算任何子矩阵(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-852786.html

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

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

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

相关文章

  • 子矩阵的和(二维前缀和)

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

    2024年02月08日
    浏览(42)
  • 利用前缀和计算二维矩阵子矩阵的和

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

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

    二维矩阵的前缀和,我们可以通过求前缀和来把求二维矩阵的求某一块的和,从时间复杂度O(n^2)变成O(1)常数级,大大降低了时间复杂度 文章目录 前言 一、二维矩阵的前缀和应该怎么做? 1.引入一个二维数组 2.二维前缀和矩阵数组 3.推出二维矩阵前缀和的公式计算 3.1 代码如

    2024年03月27日
    浏览(103)
  • C++ 二维前缀和 子矩阵的和

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

    2024年02月21日
    浏览(54)
  • 基础算法-子矩阵的和

         二维前缀和推导 如图: 紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积, 绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。 从图中我们很容易看出,整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[

    2024年02月15日
    浏览(42)
  • 【算法 | 模拟No.4】AcWing 756. 蛇形矩阵 & AcWing 40. 顺时针打印矩阵

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年01月16日
    浏览(54)
  • 【LeetCode 算法】Matrix Diagonal Sum 矩阵对角线元素的和

    给你一个正方形矩阵 mat ,请你返回矩阵对角线元素的和。 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 n = = m a t . l e n g t h = = m a t [ i ] . l e n g t h 1 = n = 100 1 = m a t [ i ] [ j ] = 100 n == mat.length == mat[i].length\\\\ 1 = n = 100\\\\ 1 = mat[i][j] = 100 n == ma t . l

    2024年02月13日
    浏览(43)
  • 【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法

    👑作者主页:@进击的安度因 🏠学习社区:进击的安度因(个人社区) 📖专栏链接:每日挠头算法题 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 链接 :756. 蛇形矩阵 输入两个整数 n 和 m ,输出一个 n 行 m 列的矩阵,将数字 1 到 n × m 按照回字蛇形填充至矩阵中。 具体矩

    2024年02月02日
    浏览(46)
  • C++前缀和算法:构造乘积矩阵

    C++算法:前缀和基础 给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ,定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件,则称 p 为 grid 的 乘积矩阵 : 对于每个元素 p[i][j] ,它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

    2024年02月08日
    浏览(49)
  • 【力扣】1588. 所有奇数长度子数组的和 <前缀和>

    给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。 示例 1: 输入:arr = [1,4,2,5,3] 输出:58 解释:所有奇数长度子数组和它们的和为: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1

    2024年02月10日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包