基础算法-子矩阵的和

简介: 与前缀和的基本思想类似,上一篇博文对前缀和有所介绍,不是很理解的友友可以阅读一下。一般的前缀和可以看作一维运算,而子矩阵的和则可以看作是二维运算,但本质也是一样的。原数组可以看作 a[i][j],s[i][j] 是所求区域的数组值和,以下图为例

基本思想

与前缀和的基本思想类似,上一篇博文对前缀和有所介绍,不是很理解的友友可以阅读一下。一般的前缀和可以看作一维运算,而子矩阵的和则可以看作是二维运算,但本质也是一样的。

原数组可以看作 a[i][j],s[i][j] 是所求区域的数组值和,以下图为例

2f1b3c4359f94362aaf4e1f98304235f.png对于求解 s[i][j] 可以通过两个 for 循环实现,比较简单,便不再赘述,公式即 s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j] 。

阴影部分的区域便是我们要求的子矩阵之和,将其设定为 Q 。即:Q = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + 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


具体实现

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q, res;
int s[N][N];
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j= 1;j<=m;j++)
        {
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(q--)
    {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        res=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        cout<<res<<endl;
        res=0;
    }
    system("pause");
    return 0;
}


相关文章
|
5月前
|
存储 算法
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
|
算法
ACM算法训练【子矩阵的和】
ACM算法训练【子矩阵的和】
71 0
ACM算法训练【子矩阵的和】
|
算法 人工智能 机器学习/深度学习
算法学习之路|poj1050(最大子矩阵和)
对于n*n的矩阵,求它的最大子矩阵和。
1451 0
|
29天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
6天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
|
14天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
15天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
16天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
15天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
15天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
34 3
下一篇
无影云桌面