二维差分详解

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

前言
上一期我们分享了一维差分的使用方法,这一期我们将接着上期的内容带大家了解二位差分的使用方法,话不多说,LET’S GO!(上一期链接)
二维差分详解,c语言学习,算法专栏,c语言,算法

二维差分
二维差分我们可以用于对矩阵区间进行多次操作的题。
二维差分我们还可以采用一维差分的思想,如图假如我们要对区间[x1,x2],[y1,y2]的元素都+1:
二维差分详解,c语言学习,算法专栏,c语言,算法
即:

        arrsum[x1][y1] += 1;
		arrsum[x1][y2+1] -= 1;
		arrsum[x2+1	][y1] -= 1;
		arrsum[x2+1][y2+1] += 1;

思路就是这样,操作完之后直接求数组全缀合就是目标矩阵数组,下面我们上实战。
给出矩阵数组arr,共有n行m列,对其进行t次操作,每次操作会对[ x1 , x2 ],[ y1,y2 ]区间内的元素+1,请输出进行操作后的arr数组。
输入样例
第一行为n,m和q
往后n行为矩阵数组的元素
往后q行为x1,y1,x2,y2
测试样例
3 3 2
1 1 1
1 1 1
1 1 1
1 1 2 2
2 2 3 3
输出样例
2 2 1
2 3 2
1 2 2
题解:

#include<stdio.h>
int arr[100][100];
int arrsum[100][100];//前缀和数组
int main()
{
	int n, m, t;
	scanf("%d %d %d", &n, &m, &t);
	for (int i = 1; i <= n; i++)//输入数组
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	for (int i = 1; i <= n; i++)//操作arrsum数组使其前缀和为目标数组
	{
		for (int j = 1; j <= m; j++)
		{
			arrsum[i][j] += arr[i][j];
			arrsum[i+1][j] -= arr[i][j];
			arrsum[i][j+1] -= arr[i][j];
			arrsum[i+1][j+1] += arr[i][j];
		}
	}
	while (t--)//t次操作
	{
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		arrsum[x1][y1] += 1;
		arrsum[x1][y2+1] -= 1;
		arrsum[x2+1	][y1] -= 1;
		arrsum[x2+1][y2+1] += 1;
	}
	for (int i = 1; i <= n; i++)//求前缀和
	{
		for (int j = 1; j <= m; j++)
		{
			arrsum[i][j] += arrsum[i-1][j]+arrsum[i][j-1]-arrsum[i-1][j-1];	
		}
	}
	for (int i = 1; i <= n; i++)//打印目标数组
	{
		for (int j = 1; j <= m; j++)
		{
			printf("%d ", arrsum[i][j]);
		}
		printf("\n");
	}
	return 0;
}

尾声
本期分享就到这里,如果觉得博主讲的不错的话请给博主一个关注,点赞,收藏支持一下吧~,博主还将持续分享更多知识,我们下期再见!文章来源地址https://www.toymoban.com/news/detail-769454.html

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

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

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

相关文章

  • 自然语言处理学习笔记(五)————切分算法

    目录 1.切分算法 2.完全切分 3.正向最长匹配 4.逆向最长匹配 5.双向最长匹配 6.速度评测 1.切分算法         词典确定后,句子可能含有很多词典中的词语,他们有可能互相重叠,如何切分需要一些规则。常用规则为: 正向匹配算法、逆向匹配算法以及双向匹配算法 。但他们

    2024年02月14日
    浏览(56)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(42)
  • 《算法导论》学习(十七)----动态规划之钢条切割(C语言)

    本文主要讲解了钢条切割问题的解决方案,并且给出了C语言代码。其中涉及到了动态规划的思想,会在之后的文章中详细讲解 Serling公司购买长钢条,将其切割成短钢条进行出售。切割工序本身没有成本支出。管理层希望得到最优的切割方法。 现在我们知道Serling公司出售一

    2023年04月23日
    浏览(42)
  • 11、动手学深度学习——语言模型和数据集:代码详解

    我们了解了如何将文本数据映射为词元,以及将这些词元可以视为一系列离散的观测,例如单词或字符。 假设长度为 T T T 的文本序列中的词元依次为 x 1 , x 2 , … , x T x_1, x_2, ldots, x_T x 1 ​ , x 2 ​ , … , x T ​ 。于是, x t x_t x t ​ ( 1 ≤ t ≤ T 1 leq t leq T 1 ≤ t ≤ T )可以

    2024年02月17日
    浏览(39)
  • 《算法导论》学习(十八)----动态规划之矩阵链乘(C语言)

    本文主要讲解了动态规划中的矩阵链乘问题:给定一个矩阵链,得到它的最小代价计算次序。给出了动态规划方案的分析,并且给出了C语言实现。 给定一个n个矩阵的序列(矩阵链) A 1 , A 2 , A 3 , A 4 , . . . , A n A_1,A_2,A_3,A_4,...,A_n A 1 ​ , A 2 ​ , A 3 ​ , A 4 ​ , ... , A n ​ ,现在

    2024年02月06日
    浏览(44)
  • 机器学习中四类进化算法的详解(遗传算法、差分进化算法、协同进化算法、分布估计算法)

    GA算法原理 首先我们来介绍进化算法的先驱遗传算法,遗传算法(Genetic Algorithm,简称GA)是一种最基本的进化算法,它是模拟达尔文生物进化理论的一种优化模型,最早由J.Holland教授于1975年提出。遗传算法中种群分每个个体都是解空间上的一个可行解,通过模拟生物的进化

    2024年02月09日
    浏览(41)
  • 智能合约学习笔记一 、——{Solidity语言详解——(1—2)小练习}

    1.根据提示,在指定位置写出编译版本,要求使用^符号,版本要求在0.6.0及以上。 2.根据提示,在指定位置写出所定义的合约名称。 3.为了查看程序的效果,我们使用在线 Solidity 开发工具 Remix IDE 编译和运行 Solidity 程序。中文在线版:在浏览器打开下方链接: Remix - 中文版

    2024年02月02日
    浏览(38)
  • 二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)

    上一篇文章讲解了一维前缀和一维差分,本篇进阶为二维。 二维前缀和跟一维前缀和求法相同,这里直接上例子。 数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]] a数组如图: 则数组a的前缀和为:数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]] b数组如图: 前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1]

    2024年04月22日
    浏览(38)
  • MATLAB算法实战应用案例精讲-【深度学习】自然语言处理模型SimCSE

    目录 前言 1.介绍 2.对比学习背景 2.1定义 2.2构造正样本 2.3对齐性和均匀性

    2024年02月11日
    浏览(63)
  • (完整代码)R语言中利用SVM-RFE机器学习算法筛选关键因子

    自用生信代码, 花费一个多月写下来的。自学R以来第一次写600多行的代码。我的文章已经发表,如对您的研究有帮助希望可以引用一下。文章点我 主要是借助e1071包, 实现mSVM-REF识别并筛选关键基因,没有安装的小伙伴需要安装一下。 mSVM-REF函数是John Colby教授写的链接点我

    2023年04月24日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包