首页 > 其他分享 >子矩阵的和(二维前缀和)

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

时间:2023-10-18 21:12:13浏览次数:34  
标签:x1 前缀 int 矩阵 x2 二维 y1 y2

一、算法描述

上一篇文章介绍了一维前缀和,也就是一个数组的前n项和,这篇文章来介绍一下什么是二维前缀和。

含义

  • 一维的是前n项的和,那么二维的情况下,表示的则是与左上角形成的矩形和。

怎么求

  • 一维的递推关系式是s[i] = s[i - 1] + a[i];,我们根据含义来思考二维的递推关系式,读者可以在草稿纸上画一个矩形来更好的理解。

  • \(s[i][j]\) 表示的是 \(i, j\) 这个位置与左上角形成的矩形和,\(s[i - 1][j]\) 表示的是比 \(s[i][j]\) 少一行的矩形和, \(s[i][j - 1]\) 表示的是比 \(s[i][j]\) 少一列的矩形和。

  • 用 \(s[i - 1][j] + s[i][j - 1]\) 得到的就是 \(s[i][j]\) ,但是少了一个 \(a[i][j]\) ,同时多了一个 \(i - 1, j - 1\) 与左上角形成的矩形和,即 \(s[i - 1][j - 1]\)。

  • 综上可以得到求得 \(s[i][j]\) 的递推关系式为:s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];,读者应在草稿纸上自己推理,不要纯靠记忆。

怎么用

  • 一维前缀和的用法在 \(O(1)\) 的时间复杂度内求得 \([l, r]\) 的区间和,那么二维前缀和则是在 \(O(1)\)的时间复杂度内求得 \([x1, y1]\) 到 \([x2, y2]\)这个区域的矩形和。

  • 显然我们要用 \(s[i][j]\) 这块大面积来减去其他的面积,那么需要减去哪些部分呢?大家自行在草稿纸上推演,计算如下:s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];,根据含义来思考如何推算。

二、题目描述

输入一个 \(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算法基础课-796.子矩阵的和

四、源代码

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
        
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++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;
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
    
    return 0;
}

标签:x1,前缀,int,矩阵,x2,二维,y1,y2
From: https://www.cnblogs.com/grave-master/p/17773172.html

相关文章

  • 证明反对称矩阵的秩是偶数
    对反对称矩阵消元,如果有非零元素,不妨假设\(a_{1,2}\neq0\)。定义对\((i,j,k)\)使用操作1表示,第\(i\)行\(\timesk\)加到第\(j\)行然后第\(i\)列\(\timesk\)后加到第\(j\)列。注意到操作完仍是反对称矩阵。可以使用操作1把所有第一行第二行,第一列第二列除了......
  • 2023-10-18:用go语言,给定一个数组arr,长度为n,表示有0~n-1号设备, arr[i]表示i号设备的型
    2023-10-18:用go语言,给定一个数组arr,长度为n,表示有0~n-1号设备,arr[i]表示i号设备的型号,型号的种类从0~k-1,一共k种型号,给定一个k*k的矩阵map,来表示型号之间的兼容情况,map[a][b]==1,表示a型号兼容b型号,map[a][b]==0,表示a型号不兼容b型号,兼容关系是有向图,也就是a型号兼容b型号......
  • 小白学算法-什么是矩阵数据结构以及有哪些应用?
    什么是矩阵数据结构以及有哪些应用矩阵表示按行和列的顺序排列的数字的集合。必须将矩阵的元素括在圆括号或方括号中。例如:具有9个元素的矩阵如下所示。该矩阵M有3行和3列。矩阵M的每个元素都可以通过其行号和列号来引用。例如,M[2][3]=6。矩阵是由行和列组成的二维数组。......
  • 邻接矩阵
    邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。  设一个图G=(V,E)逻辑结构分为两部分:V和E集合,其中,V是顶点,E是边。用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。......
  • CSS3属性详解(一)文本 盒模型中的 box-ssize 属性 处理兼容性问题:私有前缀 边框 背
    CSS3是用于为HTML文档添加样式和布局的最新版本的层叠样式表(CascadingStyleSheets)。下面是一些常用的CSS3属性及其详细解释:border-radius:设置元素的边框圆角的半径。可以使用四个值设置四个不同的圆角半径,也可以只使用一个值来设置统一的圆角。box-shadow:创建一个元素的阴影效果......
  • 矩阵求导笔记
    1.标量对矩阵的求导考虑一个标量函数\(f(A)\),其输入是一个\(m\timesn\)矩阵。函数关于矩阵的导数定义为:\[\frac{\partialf}{\partialA}=\begin{bmatrix}\frac{\partialf}{\partialA_{11}}&\cdots&\frac{\partialf}{\partialA_{1n}}\\\vdots&\d......
  • 【前缀和优化 dp】CF1542E2 Abnormal Permutation Pairs (hard version) 题解
    CF1542E2首先时间复杂度肯定是\(\mathcal{O}(n^3)\)的。容易想到先枚举最长公共前缀,然后枚举\(p_{len+1}\)和\(q_{len+1}\),再枚举逆序对数进行统计。令\(f_{i,j}\)表示有\(j\)个逆序对的\(i\)阶排列的个数。易得转移\(f_{i,j}=\sum\limits_{k=\max(j-i+1,0)}^{j}f......
  • ZXing.Net 的Core平台生成二维码
    一、引用二、代码帮助类///<summary>///ZXing.NET二维码帮助类///</summary>publicclassZXingHelper{///<summary>///站点二维码的目录///</summary>privatestaticstringQRCodeDirectory="QRCode";......
  • Julia notebook:矩阵乘法
    在本次notebook中,我们将:并行化一个简单的算法学习不同并行策略的performance使用Julia进行实现 问题描述假设所有矩阵,包括A,B和C都初始存储在masterprocess最终的结果会将在C中被覆盖步骤为了实现并行化,我们将遵循以下步骤:确定顺序算法中可以并行化的部分考虑......
  • 稀疏矩阵快速转置
    如果需要将一个使用三元组形式存储的稀疏矩阵进行转置,当然可以直接交换每一个结点的行和列。但这样做的问题在于,原矩阵是按行数升序排列的,转置之后的矩阵就会变为无序的。快速转置算法的目的就在于得到一个同样有序排列的转置后矩阵。三元组和稀疏数组定义#defineMAXSIZE1250......