C++ 二维前缀和 子矩阵的和

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

输入一个 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
C++ 二维前缀和 子矩阵的和,前缀和,力扣,算法笔记,c++,矩阵,算法
C++ 二维前缀和 子矩阵的和,前缀和,力扣,算法笔记,c++,矩阵,算法文章来源地址https://www.toymoban.com/news/detail-834133.html

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main ()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            
    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;
}

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

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

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

相关文章

  • 二维前缀和公式 AcWing 796. 子矩阵的和

    记住两个公式就行 不知道算难还是算简单,公式就是代码里面写的那样,完完全全公式,没有任何其他东西

    2024年02月19日
    浏览(46)
  • 【力扣】304. 二维区域和检索 - 矩阵不可变 <二维前缀和>

    给定一个二维矩阵 matrix ,以下类型的多个请求: 计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。 实现 NumMatrix 类: NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, co

    2024年02月10日
    浏览(39)
  • 【算法思考记录】【前缀和,C++】力扣1277. 统计全为 1 的正方形子矩阵

    原题链接 题目要求我们统计在一个由0和1构成的矩阵中,所有完全由1组成的正方形子矩阵的数量。这是一道中等难度的算法题目,其关键在于高效地计算出不同大小的正方形子矩阵是否完全由1组成。 解决此问题的一个有效方法是使用 前缀和 算法。前缀和是一种预处理技术

    2024年02月03日
    浏览(38)
  • C++ 二维差分 二维前缀和逆运算 差分矩阵

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c ,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c 。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数

    2024年02月21日
    浏览(55)
  • 【力扣】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)
  • 《剑指 Offer》专项突破版 - 面试题 13 : 二维子矩阵的数字之和(C++ 实现)- 二维前缀和

    题目链接 :LCR 013. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode) 题目 : 输入一个二维矩阵,如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和?对于同一个二维矩阵,计算子矩阵的数字之和的函数可能由于输入不同的坐标而反复调用多次。 例如,对于下图中的二

    2024年01月18日
    浏览(40)
  • 【算法详解】力扣240.搜索二维矩阵II

    力扣链接:力扣240.搜索二维矩阵II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 题目提到该矩阵是从左到右,从上到下递增的,那么我们就要利用这个性质,从矩阵

    2024年01月21日
    浏览(46)
  • 前缀和例题:子矩阵的和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日
    浏览(44)
  • C++前缀和算法:构造乘积矩阵

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

    2024年02月08日
    浏览(49)
  • 【算法】在二维不单调的矩阵上二分查找——力扣1901. 寻找峰值 II

    1901. 寻找峰值 II 给定一个从0开始编号的m x n矩阵 mat ,其中任意两个相邻格子的值都不相同。峰值是指那些严格大于其相邻格子(上、下、左、右)的元素。需要找出任意一个峰值 mat[i][j] 并返回其位置 [i, j] 。 示例 1: 示例 2: 步骤一:列转行 首先,将矩阵的列转换为行,表示为

    2024年02月03日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包