差分算法及模板详解

时间:2024-01-10 01:03:08 标签:  # 算法基础教程  算法  c++  数据结构  差分算法  

⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的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之后的数组又会恢复原值,仅需要处理这两个边界的差分数组即可,时间复杂度大大降低。

image-20220915162819362

例题:差分

输入一个长度为 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]的和即可。如下所示:

image-20220919221638474

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

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

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;

image-20220919222657158

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

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

输出样例:

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;
}
来源:https://blоg.сsdn.nеt/m0_52316372/аrtiсlе/dеtаils/127259881

智能推荐

一维差分数组假设给你一个数组 nums ,先对区间 [a,b] 中每个元素加 3 ,在对区间 [c,d] 每个元素减 5 …… ,这样非常频繁的区间修改,常规的做法可以一个个计算。public void increment(int[] nums, int a, int b, int k) { for (int index = a; index <= b; index++) { nums[index] += k; }}频繁对数组的一段区间进行增加或减去同一个值,如果一个个去操作,很明显

标签:数组  详解  差分  

摘要:Raft算法是一种分布式共识算法,用于解决分布式系统中的一致性问题。本文分享自华为云社区《共识算法之Raft算法模拟数》,作者: TiAmoZhang 。01、Leader选举存在A、B、C三个成员组成的Raft集群,刚启动时,每个成员都处于Follower状态,其中,成员A心跳超时为110ms,成员B心跳超时为150ms,成员C心跳超时为130ms,其他相关信息如图1所示。

标签:算法  共识  详解  Raft  

P8436 【模板】边双连通分量概念注意!双连通仅针对无向图而言。割边(桥):删去这条边使图不连通的边。边双连通图:不存在割边的图(等价定义:图中任意两个点都至少两条不同路径可以到达的图)。性质:一个点不可能同时属于2个边双连通图,因为如果两个双连通分量相交与一点,那么删去任意一条边,两个子图之间仍然连通 , 故“属于同一个双连通图”的关系是具有传递性的。

标签:双连  分量  模板  详细  

一,前言1.1,模型剪枝定义二,深度神经网络的稀疏性2.1,权重稀疏2.2,激活稀疏2.3,梯度稀疏2.4,小结三,结构化稀疏3.1,结构化稀疏分类3.1.1,Channel/Filter 剪枝3.1.2, 阶段级别剪枝3.2,结构化稀疏与非结构化稀疏比较参考资料一,前言学术界

标签:算法  详解  模型  

概述lua字符串通过操作算法和内存管理,有以下优点:节省内存。字符串比较效率高。(比较哈希值)问题:相同的字符串共享同一份内存么?相同的长字符串一定不共享同一份内存么?lua字符串如何管理内存?数据结构lua字符串TStringtypedef struct TString { CommonHeader; lu_byte extra; /* reserved

标签:数据结构  算法  详解  源码  操作  

转自XGBoost XGBoost XGBoost全名叫&#xf

标签:xgboost  机器学习  决策树  算法  

猜你喜欢

最近有很多朋友咨询我关于Matlab论文插图绘制方面的问题。 问了一下&#xff

标签:Matlab插图  MATLAB  开发语言  

差模干扰(差模信号)是一种在差分信号传输系统中出现的干扰模式,这种干扰模式主要是由于电路板上两条差分信号线的长度、宽度和间距等参数不一致所导致的。如果不采取有效的措施进行抑制和消除,差模干扰会对电路板中的信号传输产生不良影响,可能导致系统运行不稳定、数据传输错误等问题。为了消除差模干扰,可以采取以下几种方法:设计合适的滤波器,过滤差模信号中的高频成分,以减少差模干扰的影响。增加信号线的屏蔽措施,如采用金属编织网等,以减小外界电磁场的干扰。对信号线进行良好的布局和走线,以减小信号线之间的耦合程度和互相干扰。对电路板进行接地设计,通过接地层将差分信号的地线连接起来,以减小共模噪声的影响。使用信号放大器等元件进行信号处理,以提高信号质量并减小差模干扰

标签:干扰  

基本介绍模板方法模式 是在一个固定步骤的方法骨架中,将某些步骤延迟到子类实现,以便重新定义该方法中的某些特定步骤。模板方法模式属于行为型模式,较为简单。&nbsp;假设我们开了一家早餐店,每天早上一大早我们就要研磨豆浆,研磨豆浆的步骤都是特定的,只是原材料不同,它们都要进行 选材 -》 添加配料 -》 浸泡 -》 放到豆浆机研磨添加不同的配料可以制作不同口味的豆浆选材、浸泡以及豆浆机研磨这几个步骤对于每种口味的豆浆而言都是相同的

标签:模板  模式  方法  

一、模板方法模式介绍1、定义与类型定义:定义了一个算法的骨架,并允许子类为一个或多个步骤提供实现模板方法使得子类可以在不改变算法结构的情况下,重新定义算法的某些步骤类型:行为型2、适用场景一次性实现一个算法的不变的部分,并将可变的行为留给子类来实现各子类中公共的行为被提取出来并集中到一个公共父类中,从而避免代码重复3、优点提高复用性提高扩展性符合开闭原则4、缺点类数目增加

标签:模板  模式  方法  

本题要求实现一个Vector类模板&#xff0c;能实现数据的存储和访问。通过[]

标签:PTA习题解  c++  开发语言  数据结构  

摘要:本文主要为大家讲解关于深度学习中几种模型压缩技术、模型蒸馏算法:Patient-KD、DistilBERT、DynaBERT、TinyBERT。本文分享自华为云社区《深度学习实践篇[17]:模型压缩技术、模型蒸馏算法:Patient-KD、DistilBERT、DynaBERT、TinyBER》,作者: 汀丶。1.模型压缩概述1.1模型压缩原有理论上来说,深度神经网络模型越深,非线性

标签:模型  算法  详解  压缩技术  

什么是贪心 贪心的本质是选择每一阶段的局部

标签:贪心算法  算法  leetcode  

模板方法模式1.定义定义一个操作中的算法的框架,而将一些步骤的实现延迟到子类中,使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。使用模板方法模式制造两款汽车。定义汽车必须有的特质:能够发动,鸣笛和停止,不同型号的汽车实现不同。汽车生产完成后需要对汽车的质量进行检验,测试汽车的所有功能。抽象汽车模型(抽象汽车类)public abstract class AbstractCar { // 汽车可以发动,发动方式不同,需要在实

标签:模板  模式  方法  TemplateMethodPattern  

转载请注明出处。全网@秋意正寒1. 瓦片的调度查阅 tileset.json 的规范,有一个属性是 refine,它有两个值:ADD 和 REPLACE。还有另一个属性,叫 geometricError,是一个数字。ADD 的含义是,当这一级瓦片显示不够精细时,渲染下一级瓦片,这一级的瓦片保留继续显示(增加下一级的内容)。REPLACE

标签:误差  几何  详解  dTiles  

1、差分方程基础概念&#xff1a; 差分&#xff1a;

标签:数学建模  数学  

简介模板方法模式(Template Method Pattern)也叫模板模式,是一种行为型模式。它定义了一个抽象公开类,包含基本的算法骨架,而将一些步骤延迟到子类中,模板方法使得子类可以不改变算法的结构,只是重定义该算法的某些特定步骤。不同的子类以不同的方式实现这些抽象方法,从而对剩余的逻辑有不同的实现。以此基于公共的模板,来实现实现不同的功能。模板模式适用于一些复杂操作进行步骤分割、抽取公共部分由抽象父类实现、将不同的部分在父类中定义抽象实现、而将具体实现过程由子类完成。对于有多个子类具有共有的方法,且逻辑相同,可以考虑作为模板方法。作用相同的部分父类给出统一的模板,子类大量复用,从而节省代码,复用

标签:详解  模板  语言  模式  方法  

Sobel算子是一种经典的边缘检测算子&#xff0c;被广泛应用于图像处理领域。它基于图像亮度的变化

标签:计算机视觉  深度学习  人工智能  

相关问题

相关文章

热门文章

推荐文章

相关标签