差分详细讲解(C++)

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

每日一句:平凡的我在人多的地方曾极力小心翼翼, 但不知从何时起 ,我不太在意别人的目光了。比起被人觉得是个怪人,我现在更害怕浪费时间。


一、一维差分

差分就是前缀和的逆运算,如果你不懂什么是前缀和,看这里->前缀和详解

数组a:a[1], a[2], a[3], a[n]
数组b : b[1] ,b[2] , b[3], b[i]
使得 a数组是b数组的前缀和,b数组是a数组的差分
a[i] = b[1] + b[2] + …+ b[i]

数字来看的话就是这样的:
a数组1 3 7 5 2
b数组1 2 4 -2 -3
Sumb数组1 1+2 1+2+4 1+2+4-2 1+2+4-2-3
----------也就是1 3 7 5 2跟原数组还是相同的
a是b的前缀和,b是a的差分.

那么,问题来了,差分有什么用呢?

当你把一个区间[L,R]的数都加上或减去某一个数x的时候,该怎末做呢?第一时间想到的肯定是暴力做法,输入LR区间,然后for循环,直接暴力解决,确实暴力解法能解决很多事情,但是时间复杂度很高,为O(n),如果想进行m次区间加上或减去x的操作呢?每次都遍历LR区间,那么时间复杂度就更高了O(n*m).这个时候,就有人对其优化,想出来了一种名为差分的解法,差分解法呢,有一个公式:[L,R] + X <==>差分数组[L] + X,差分数组[R+1] - X;
那么,这个公式是怎么来的?
差分详细讲解(C++)
下面看一道例题:

输入一个长度为 n 的整数序列。

接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数序列。

接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。

输出格式

共一行,包含 n 个整数,表示最终序列。

数据范围

1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000

输入样例:

—6 3
—1 2 2 1 2 1
—1 3 1
—3 5 1
—1 6 1

输出样例:

3 4 5 3 4 2

1.先输入数组

	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

然后把原数组a,变成差分数组b

	void insert(int l, int r, int c)
	{
		b[l] += c;
		b[r + 1] -= c;
	}


	for (int i = 1; i <= n; i++)
	{
		insert(i, i, a[i]);
	}

对差分数组进行m次操作

	while (m--)
	{
		int l, r, c;
		cin >> l >> r >> c;
		insert(l, r, c);
	}

最后,将差分数组变回原数组

	for (int i = 1; i <= n; i++)
	{
		b[i] += b[i - 1];
		cout << b[i] << ' ';
	}

总代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N];

int b[N];

void insert(int l, int r, int c)
{
	b[l] += c;
	b[r + 1] -= c;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++)
	{
		insert(i, i, a[i]);
	}

	while (m--)
	{
		int l, r, c;
		cin >> l >> r >> c;
		insert(l, r, c);
	}

	for (int i = 1; i <= n; i++)
	{
		b[i] += b[i - 1];
		cout << b[i] << ' ';
	}


	return 0;
}

题目来源acwing799

二、二维差分

二维差分也就是二维前缀和的逆运算,其构造差分的过程和构造一维差分的过程差不多类似.在这里主要说一下构造过程:

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;
}

标红区区域便是x1,y1进行区间加或减操作的区域

差分详细讲解(C++)

黄色和咖啡色区域便是x2+1,y1和x1,y2+1的区间,而有x2+1,y2+1的区间是重叠的部分,也就是说,在 b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c;这两部中,x2+1,y2+1被多减了一次,所以要把这部分还回去,也就是这一步 b[x2 + 1][y2 + 1] += c;

差分详细讲解(C++)

下面看一到例题

输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q。

接下来 n 行,每行包含 m 个整数,表示整数矩阵。

接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作 。

输出格式

共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000

输入样例

3 4 3

1 2 2 1

3 2 2 1

1 1 1 1

1 1 2 2 1

1 3 2 3 2

3 1 3 4 1

输出样例:

2 3 4 1

4 3 4 1

2 2 2 2

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
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()
{
    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++)
            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]);
        puts("");
    }

    return 0;
}

题目来源acwing800文章来源地址https://www.toymoban.com/news/detail-436216.html

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

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

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

相关文章

  • 平凡工作也能实现奇迹:学习 ai 公文的写作逻辑和技巧

    如何把平凡的工作写出光环 📜 很多初入职场的人在撰写个人先进事迹材料时面临的最大问题是:他们认为自己做的工作都是琐碎且普通的,没有任何惊天动地的成就或值得称赞的成绩。因此,他们感到非常困惑,不知道该如何撰写他们的日常工作。实际上,将平凡的工作描

    2024年02月08日
    浏览(54)
  • 平凡的Python为什么能一跃成为世界排名第一的语言

    本文首发自「慕课网」,想了解更多IT干货内容,程序员圈内热闻,欢迎关注\\\"慕课网\\\"! 作者:大周|慕课网讲师 本文将结合个人经历为各位同学客观的分析是否有学习Python的必要、Python适合谁学、为什么要学,希望能够给看到此文章的同学一点建议,树立学习目标,让学习有

    2023年04月18日
    浏览(62)
  • 二维前缀和&二维差分(超详细,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日
    浏览(41)
  • uniapp - 超详细实现播放 svg / svga 格式动画组件插件,用于直播间赠送礼物特效动画或项目动画特效较多的应用(新手小白保姆级教程,提供插件+详细运行示例+使用文档+注意事项+格式说明)

    网上关于 uniapp 播放 svg / svga 格式动画的教程很乱,基本上全是 BUG 和各种不兼容,很难复制过来自己用。 本文实现了 在 uniapp 项目中(完美兼容 H5 / App / 微信小程序平台),播放 svg / svga 格式动画功能的详细介绍, 您只需要使用我提供的 “组件源码及插件”,放到项目中去

    2023年04月24日
    浏览(197)
  • 哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)

    目录 一、哈夫曼树    1.哈夫曼树的基本概念    2.哈夫曼树的构造过程    3.哈夫曼树的的实现 二、哈夫曼编码     1.有关哈夫曼树编码的两个概念     2.哈夫曼树编码满足的两个性质     3.哈夫曼编码的实现 三、例题(含完整代码及详细注解)     1.题目     2.代码实现

    2024年02月07日
    浏览(51)
  • QT入门看这一篇就够了——超详细讲解(40000多字详细讲解,涵盖qt大量知识)

    目录 一、Qt概述 1.1 什么是Qt 1.2 Qt的发展史 1.3 Qt的优势 1.4 Qt版本 1.5 成功案例 二、创建Qt项目 2.1 使用向导创建 2.2 一个最简单的Qt应用程序 2.2.1 main函数中 2.2.2 类头文件 2.3 .pro文件 2.4 命名规范  2.5 QtCreator常用快捷键 三、Qt按钮小程序 3.1按钮的创建和父子关系 3.2 Qt窗口坐标

    2024年02月09日
    浏览(50)
  • 华为静态路由配置实验(超详细讲解+详细命令行)

    前言 一,静态路由配置 二,网络地址配置 AR1的配置: AR2的配置: AR3的配置: 三,测试是否连通 AR1的配置: 讲解: AR2的配置: 讲解: 四,AR3配置回环ip地址 讲解: 五,配置静态路由表 AR1的配置: 讲解: AR2的配置: AR3的配置: 六,测试回环地址是否能通 AR1的配置: 讲解:

    2024年02月10日
    浏览(39)
  • Java 抽象类详细讲解

    目录 Java抽象类概念 Java抽象类示例 继承Animal类的子类的示例 Java抽象类详细使用方法 1、定义抽象类 2、继承抽象类 3、实现抽象方法 4、完整示例代码 Java中抽象类是指用abstract修饰的类,它不能被实例化,只能被继承。抽象类通常用于定义一些公共的方法和属性,但是

    2023年04月18日
    浏览(37)
  • 如何使用ActiveMQ详细讲解

    ActiveMQ 是一款流行的消息中间件,支持多种通信协议和消息模式,包括点对点、发布/订阅、事务处理等。下面是使用 ActiveMQ 的基本步骤: 1. 下载和安装 ActiveMQ: 2. 启动 ActiveMQ 服务器: 3. 访问 ActiveMQ 的 Web 控制台: 4. 创建队列或主题: 5. 发送消息: 6. 接收消息: 以上是使

    2024年01月17日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包