差分算法及模板详解

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

⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法复习。

差分

一维差分

差分思想和前缀和是相反的。

首先我们先定义数组a, 其中a[1],a[2]…a[n]作为前缀和。

然后构造数组b,b[1],b[2]…b[n]为差分数组。其中通过差分数组的前缀和来表示a数组,即a[n] = b[1] + b[2]+…+b[n]。

一维差分数组的构造也很简单,即a[1] = b[1], b[2] = a[2] - a[1], b[n] = a[n] - a[n-1];

注意:刚开始时可以初始化数组a,b全部为0,输入a数组后;在构造时,只需要将b[1]看做在[1, 1]区间上加上a[1]; b[2] 看作在[2, 2]区间上加上a[2];

//eg:对于b[1]:
b[1] = 0 + a[1];
b[2] = 0 - a[1]; 	//最终:b[1] = a[1]
//对于b[2]:
b[2] = b[2] + a[2];  //==> 最终:b[2] = a[2] - a[1]
b[3] = b[3] - a[2];

差分数组的好处是可以简化运算,例如想要给一个区间 [l,r] 上的数组加一个常数c,原始的方法是依次加上c,这样的时间复杂度是O(n)的。但是如果采用差分数组的话,可以大大降低时间复杂度到O(1)。

由于a[n] = b[1] + b[2]+…+b[n],因此只需要将b[l] = b[l] + c 即可,这样l之后的数字会依次加上常数c,而在 b[r]处,将b[r+1] = b[r+1] - c ,这样r之后的数组又会恢复原值,仅需要处理这两个边界的差分数组即可,时间复杂度大大降低。

差分算法及模板详解

例题:差分

输入一个长度为 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
代码模板
#include<iostream>
using namespace std;

const int N = 100010;

int m,n;
int a[N],b[N];

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

int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
    //插入的方式形成b[i]
    for(int i = 1; i <= n; i++) insert(i, i, a[i]);
    
    while(m--)
    {
        int l, r ,c;
        scanf("%d%d%d",&l, &r, &c);
        insert(l, r, c);
        
    }
    for(int i = 1; i <= n; i++) b[i] += b[i - 1];
    
    for(int i = 1; i <= n; i++) printf("%d ", b[i]);
    
    return 0;
}

二维差分

将a[i][j]表示为一个差分数列b[i][j]的和即可。如下所示:

差分算法及模板详解

基本思路:给其中的一个子矩阵加上一个值。矩阵以外的减去一个值即可。

可列公式表示各个范围如下:

b [ x 1 ] [ y 1 ] + = C ; b[x_1][y_1] += C; b[x1][y1]+=C;

b [ x 1 ] [ y 2 + 1 ] − = C ; b[x_1][y_2 + 1] -= C; b[x1][y2+1]=C;

b [ x 2 + 1 ] [ y 1 ] − = C ; b[x_2 + 1][y_1] -= C; b[x2+1][y1]=C;

b [ x 2 + 1 ] [ y 2 + 1 ] + = C ; b[x_2 + 1][y_2 + 1] += C; b[x2+1][y2+1]+=C;

差分算法及模板详解

由上面范围,可以求得最终要算的小正方形的面积公式:

S = b [ x 1 ] [ y 1 ] − b [ x 1 ] [ y 2 + 1 ] − b [ x 2 + 1 ] [ y 1 ] + b [ x 2 + 1 ] [ y 2 + 1 ] S = b[x_1][y_1] - b[x_1][y_2 + 1]- b[x_2 + 1][y_1] + b[x_2 + 1][y_2 + 1] S=b[x1][y1]b[x1][y2+1]b[x2+1][y1]+b[x2+1][y2+1]

矩阵的初始化;

假定a[i][j] = 0,b[i][j] =0,然后读取数组a,只需要对b进行插入即可。b[i][j]相当于从(i,j)到(i,j)插入一个a[i][j]形成的。

最后求a[i][j]只需要求解b[i][j]的前缀和即可。

例题:差分矩阵

输入一个 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

输出样例:文章来源地址https://www.toymoban.com/news/detail-407360.html

2 3 4 1
4 3 4 1
2 2 2 2
代码模板
#include<iostream>
using namespace std;

const int N =1010;

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

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, x2, y1, 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;
}

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

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

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

相关文章

  • DevOps系列文章 之GitLabCI模板库的流水线

    目录结构,jobs目录用于存放作业模板。templates目录用于存放流水线模板。这次使用​ ​default-pipeline.yml​ ​作为所有作业的基础模板。 作业模板 作业分为Build、test、codeanalysis、artifactory、deploy部分,在每个作业中配置了rules功能开关,由变量控制最终作业的运行。 jobs/buil

    2024年02月16日
    浏览(52)
  • 详解DEDECMS织梦模板随机调用文章数据方法汇总教程

    有时我们为了网站优化都会对网站最后一些文章停止随机读取显现,这样能够进步网站对搜索引擎的体验,下面我们就来剖析总结一下dedecms随机调用文章数据办法. 方法一 ,直接利用artlist中的orderyb=rand 即可实例,代码如下: 代码如下: [field:title/]{/dede:arclist} 方法二 ,利用自定做法

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

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

    2024年02月09日
    浏览(44)
  • 微服务系列文章 之SpringBoot之定时任务详解

    使用SpringBoot创建定时任务非常简单,目前主要有以下三种创建方式: 一、基于注解(@Scheduled) 二、基于接口(SchedulingConfigurer) 前者相信大家都很熟悉,但是实际使用中我们往往想从数据库中读取指定时间来动态执行定时任务,这时候基于接口的定时任务就派上用场了。 三、

    2024年02月16日
    浏览(37)
  • 微服务系列文章 之 nginx日志配置指令详解

    日志对于统计排错来说非常有利的。本文总结了nginx日志相关的配置如access_log、log_format、open_log_file_cache、log_not_found、log_subrequest、rewrite_log、error_log。 nginx有一个非常灵活的日志记录模式。每个级别的配置可以有各自独立的访问日志。日志格式通过log_format命令来定义。ngx_

    2024年02月16日
    浏览(48)
  • 微服务系列文章 之 Nginx状态监控日志分析详解

    1、Nginx状态监控 Nginx提供了一个内置的状态信息监控页面可用于监控Nginx的整体访问情况,这个功能由ngx_http_stub_status_module模块进行实现。 使用nginx -V 21 | grep -o with-http_stub_status_module命令检测当前Nginx是否有status功能,如果输出ngx_http_stub_status_module则说明是有的,如果没有可以

    2024年02月16日
    浏览(52)
  • FPGA经验谈系列文章——FPGA开发方向以及算法开发模型

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 FPGA开发笼统的说可以分为两个方向,一个是接口方向、一个是算法方向。 接口方向可不是简单的uart、IIC、SPI等这些简单接口,这些东西不足以支撑一个方向,大部分都是基于serdes的高速复杂接口,例如

    2023年04月10日
    浏览(66)
  • 【C++系列P7】格式与实例化操作——[模板]详解

     前言 大家好吖,欢迎来到 YY 滴 C++系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁,主要内容含 目录 一.模板  1.函数模板 一.函数模板概念 二.函数模板的格式 三.函数模板的实例化  1.隐式实例化 2.显式实例化  3.模板参数的匹配原则  2.类模板 一.类模板的格式 二

    2024年02月10日
    浏览(42)
  • 算法模板之栈图文详解

    🌈个人主页: 聆风吟 🔥系列专栏: 算法模板、数据结构 🔖少年有梦不应止于心动,更要付诸行动。      💬 hello! 各位铁子们大家好哇,我们上期已经学习了双链表的算法模板,不知道大家都已经掌握了吗?如果你还有缺漏可以通过下面专栏自行跳转学习,今天作者

    2024年02月04日
    浏览(35)
  • 【蓝桥模板】——考试倒计时3天,你和省一就差这最后10分了(差分模板)

    全文目录🧭 🎁差分模板 🌲差分-树木上药 🚀传送锚点  💡思路点拨 🍞代码详解    🎄差分-小明的彩灯 🚀传送锚点​  💡思路点拨 🍞代码详解  差分三部曲=差分相减+转换加减+前缀相加 参考资料:原理解释 样例解释 老规矩,先来一道差集的经典例题「 树木上药 」

    2024年01月20日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包