差分矩阵算法

news/2024/11/9 9:52:00/

前言:我们熟悉一维数组的前缀和和差分数组的相关操作和原理,但是对于二维数组也就是矩阵来说,它的差分和前缀和又会有什么不同之处呢?下面我们一起来研究,

1.二维数组的前缀和

首先,我们一般规定二维数组的前缀和为由坐标(1,1)到(i,j)所围成的矩形的区域中的所有元素的总和。

我们的重点就是落在如何求子矩阵的前缀和,这是一般的题目要考察的,我们下面来分析:

所以,经过以上分析,我们可以直接给出矩阵求前缀和和子矩阵和的参考代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m,q;
int a[maxn][maxn], sum[maxn][maxn];
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]);sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];//(1,1)到(i,j)的前缀和}for (int i = 0; i < q; i++){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);printf("%d\n", sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);}return 0;
}

 怎么样,是不是挺简单的?那么好,我们要上点难度了~~~

2.差分矩阵

这里我们需要知道前缀和与差分的关系:我们知道,通过差分数组可以求出原数组中每个元素的值,并且,我们可以发现,其实原数组就是差分数组的前缀和这一点十分重要

类比一下一维差分,一维差分是在一段上加上某个值,所以我们的二维差分就可以定义为将一个子矩阵的每个元素都加上某个数

有了差分数组与原数组的关系,我们可以创建一个差分数组用于,这个数组性质就是可以像前面求前缀和一样求出原数组的每一个元素的值,而对于一个差分矩阵,我们对其中的某个元素加上一个值,影响的将是所有计算前缀和中包含该元素的部分,这点也十分重要,我们来用图说明一下,差分矩阵的效果:

 

这一部分真的需要自己真正的理解,我自己深有体会,别人的理解毕竟很大程度上说不出来,

下面给出一道例题和代码进行理解:

 

 下面是代码:

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)//差分矩阵的核心
{b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}
int main()
{int n, m, q;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++){insert(i, j, i, j, a[i][j]);      //构建差分数组,这里相当于以一个只有一个元素的矩阵插入}}while (q--){int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);//受影响的边界将被改变}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //改变的边界进而影响二维前缀和即原数组,这里也体现了差分数组的前缀和就是原数组}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){printf("%d ", b[i][j]);}printf("\n");}return 0;
}


http://www.ppmy.cn/news/42741.html

相关文章

异步框架FastAPI使用教程完整【附安装实现代码】

FastAPI是一个高性能、易于使用、快速编写API的异步框架。下面是FastAPI在实际开发中的使用步骤&#xff1a; 安装FastAPI和uvicorn pip install fastapi pip install uvicorn 编写应用代码 在一个Python文件中&#xff0c;导入FastAPI并创建一个应用对象&#xff0c;然后…

电商项目8:平台属性

电商项目8&#xff1a;平台属性1、后端1.1、属性分组模糊查询1.2、商品属性新增功能&#xff1a;保存关联关系1、后端 1.1、属性分组模糊查询 需要改造。当前端传0时候。模糊查询功能有点问题 AttrGroupServiceImpl Overridepublic PageUtils queryPage(Map<String, Obje…

【JVM】JMM

一、JMM JVM 内存模型是用来屏蔽掉各种硬件和操作系统的内存访问差异&#xff0c;以实现让 Java 程序在各个平台下都能达到一致的内存访问效果。JVM 内存模型规定了所有的共享变量都是存储在主内存&#xff0c;每个线程还有自己的工作内存&#xff0c;线程的工作内存保存了该线…

【JSON学习笔记】2.JSON vs XML及JSON的对象和数组

前言 本章介绍JSON vs XML及JSON的对象和数组。 JSON vs XML JSON 和 XML 都用于接收 web 服务端的数据。 JSON 和 XML在写法上有所不同&#xff0c;如下所示&#xff1a; JSON 实例 {"sites": [{ "name":"csdn教程" , "url":&q…

Nginx安装注意事项

一.看你是什么系统,先从官网下载你想要的版本 二.windows系统 直接解压就行了 conf 是放配置文件的地方 html是 放页面的位置 ,欢迎页也在这里 有什么静态资源也可以放这里 logs 放日志文件 在路径栏位置直接cmd 开启命令窗口 注意这里是在nginx.exe文件所在目录进行的…

结构型模式-桥接模式

结构型模式-桥接模式 结构型模式:桥接模式(Bridge)解决抽象和实现分离问题描述适用环境优点:缺点:违反原则:代码实现结构型模式: 桥接模式(Bridge) 解决抽象和实现分离问题 描述 将一个对象的抽象部分和实现部分分离开来,使得它们能够独立地变化,从而增强了系统…

产品经理必读|用户研究方法总结①

众所周知&#xff0c;理解用户需求&#xff0c;识别用户痛点&#xff0c;是产品或功能成型之前绕不开的过程。而要获取到用户真实的需求和痛点&#xff0c;唯一的方法就是做用户调研。而用研的方法都有哪些呢&#xff1f;今天我就来给大家分享一下行业中常见的用研方法。 用研的…

Pytorch实现FCN图像语义分割网络

针对图像的语义分割网络&#xff0c;本节将介绍PyTorch中已经预训练好网络的使用方式&#xff0c;然后使用VOC2012数据集训练一个FCN语义分割网络。 一、使用预训练好的语义分割网络 PyTorch提供了已预训练好的图像语义分割网络&#xff0c;已经预训练好的可供使用的网络模型…