差分学习笔记

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

1.前言

同步于 c n b l o g s cnblogs cnblogs 发布。

前置芝士:

  • 基本树上操作,lca。(用于树上差分。)

如有错误,欢迎各位大佬指出。(顺便复习一下远古算法。)

2.什么是差分

我们先给定一个数组 a a a,长度为 n n n,我们可以构造一个差分数组 b b b,使得对于任意的 i ( 1 ≤ i ≤ n ) i(1\le i \le n) i(1in) ∑ j = 1 i b j = a i \displaystyle\sum_{j = 1}^{i} b_j=a_i j=1ibj=ai

那么如何构建一个普通的差分数组呢?

不难想到,我们假定 a 0 = 0 a_0=0 a0=0,则此时,对于任意的 b i b_i bi,我们令它等于 a i − a i − 1 a_i-a_{i-1} aiai1,则当我们算 ∑ j = 1 i b j \displaystyle\sum_{j=1}^{i}b_j j=1ibj 时,所有 a 1 , a 2 . . . a i − 1 a_1,a_2...a_{i-1} a1,a2...ai1 都会抵消掉,只剩下 a i a_i ai,也正好满足了我们的前提条件。

3.差分数组的最普通应用

首先,我们先引入一个例题 P2367 语文成绩。题目意思大概就是说先给你一个序列,然后在进行区间加,最后求得区间的最小值即可。

而对于这种区间加减的操作,正是差分能够大展拳脚的地方。

我们先维护一个差分数组 b b b(以后皆假设差分数组为 b b b。),先将它全部初始化为0。假设当前我们面临的操作是将 [ l , r ] [l,r] [l,r] 这个区间全部加上 x x x。由于差分的前缀和便是原数组,所以我们可以一开始将 b l + x b_l+x bl+x,但是当你在算前缀和的时候,对于 r + 1 r+1 r+1 及以后的前缀和,他都会多算一个 + x +x +x,所以,为了将其抵消掉,我们需要将 b r + 1 − x b_{r+1}-x br+1x

最后,处理完这些询问之后,我们在最后求一次前缀和即可。

可以发现,差分修改操作时间复杂度为 O ( 1 ) O(1) O(1),查询时间复杂度为 O ( n ) O(n) O(n)

最后贴上一份代码:

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[5000005],c[5000005];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	while(q--)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		c[l]+=x,c[r+1]-=x;//由于是差分,将c[l]+x,但为了抵消掉它对后面的贡献,我们将 c[r+1]-x 
	}
	int minn=INT_MAX;
	for(int i=1;i<=n;++i)
	{
		c[i]+=c[i-1];//求前缀和 
		a[i]+=c[i];//原数组记得加上 
		minn=min(minn,a[i]);//最小值 
	}
	cout<<minn<<endl;
}

4.差分数组的二维形式

我们上述的,全都是一个序列(一维)的情况,但是,差分仍然可以扩展到二维。(对于其定义,与一维相类似,这里不做过多赘述)

假设我们当前修改的二维区间为 ( x 1 , y 1 ) (x1,y1) (x1,y1) ( x 2 , y 2 ) (x2,y2) (x2,y2),加上 x x x x 1 ≤ x 2 , y 1 ≤ y 2 x1\le x2,y1\le y2 x1x2,y1y2)。显然,我们一开始仍然需要将起始位置 b x 1 , y 1 + x b_{x1,y1}+x bx1,y1+x。但随即我们可以发现,对于所有 x 1 − n , y 1 − n x1-n,y1-n x1n,y1n 它的值都被加上了 x x x,但这个区间实际只能管到 ( x 2 , y 2 ) (x2,y2) (x2,y2),所以,对于 ( x 1 , y 2 + 1 ) (x1,y2+1) (x1,y2+1) 以及 ( x 2 + 1 , y 1 ) (x2+1,y1) (x2+1,y1) 以后的所有格子都是当前加不到的,所以我们又将 b x 1 , y 2 + 1 − x , b x 2 + 1 , y 1 − x b_{x1,y2+1}-x,b_{x2+1,y1}-x bx1,y2+1x,bx2+1,y1x。但随即我们又可以发现,虽然减是减了,但对于 ( x 2 + 1 , y 2 + 1 ) (x2+1,y2+1) (x2+1,y2+1) 及以后的值,在差分算前缀和时被减了两次,所以我们需要将 b x 1 + 1 , y 2 + 1 + x b_{x1+1,y2+1}+x bx1+1,y2+1+x

下面配上一个图方便理解。(图略丑,勿喷。)

差分学习笔记,算法总结,学习,笔记,算法

假设我们要区间加 ( 2 , 2 ) − ( 4 , 4 ) (2,2)-(4,4) (2,2)(4,4),其中黄色表示被 c x 1 , x 2 c_{x1,x2} cx1,x2 影响到的范围,蓝色表示 c x 1 , x 2 c_{x1,x2} cx1,x2 加后多影响到的地方,及 b x 1 , y 2 + 1 − x , b x 2 + 1 , y 1 − x b_{x1,y2+1}-x,b_{x2+1,y1}-x bx1,y2+1x,bx2+1,y1x 影响到的地方,绿色表示被黄色蓝色一起影响,最终被多减了一次,需要加 x x x 的区域。

大概就是:

void chafen(int x1,int y1,int x2,int y2,int x)
{
	b[x1][y1]+=x;
	b[x1][y2+1]-=x;
	b[x2+1][y1]-=x;
	b[x1+1][y2+1]+=x;
}

最后还是给一个比较简单的例题吧。P3717 [AHOI2017初中组]cover,虽然可以不用二维差分做,但当一个练习的板子题还是挺好的。

5.树上差分

这是一种非常常考也非常实用的一种差分形式。

我们先给出一种最基本的树上差分形式。即我们现在要完成的是将 x − y x-y xy 的路径上的所有节点 + x +x +x

然后我们给出树上差分的定义,即我们假设第 i i i 个点的点权为 a i a_i ai,然后我们维护差分数组 b b b 表示对于任意节点 i i i,使得 i i i 的所有子节点的 b b b 之和(包括他本身)为 a i a_i ai

然后,我们来处理树上差分。首先,我们可以把 x − y x-y xy 的路径看做 x − l c a ( x , y ) − y x-lca(x,y)-y xlca(x,y)y 的路径。( l c a lca lca 的求法这里不做赘述。)然后,由于我们要将这一段的路径全部加 z z z。我们可以发现,当我们对 b x , b y b_x,b_y bx,by 分别加上 z z z,就可以满足将 x − x- x 根节点的路径以及 y − y- y 根节点的路径全部 + z +z +z,但我们发现,不仅 f a l c a ( x , y ) − fa_{lca(x,y)}- falca(x,y) 根节点的路径多加了两遍 x x x,而且 l c a lca lca 这个节点被加了两次,但他只能被加一次,所以它也多加了一次。为了将这些效果抵消,我们可以在 b l c a ( x , y ) − z b_{lca(x,y)}-z blca(x,y)z,则对于 l c a ( x , y ) − lca(x,y)- lca(x,y) 根节点的路径,我们都被抵消了一次 z z z。但是,在抵消之后, f a l c a ( x , y − fa_{lca(x,y}- falca(x,y 根节点的路径我们仍然多加了一次 z z z,所以此时,我们需要将 b f a l c a ( x , y ) − z b_{fa_{lca(x,y)}}-z bfalca(x,y)z,便可以完美抵消掉了!

核心代码:

void tree(int x,int y,int z)
{
	b[x]+=z,b[y]+=z;
	b[lca(x,y)]-=z;b[fa[lca(x,y)]]-=z;
}

最后再奉上一个比较好想的例题:P6869 [COCI2019-2020#5] Putovanje

6.后记

虽然在维护序列时,我们完全可以用线段树树状数组等一列数据结构来代替差分这种查询较慢的结构,但差分终究还是一个好写好想的算法,是不容易出错的。毕竟,如果考场上你在面临树上路径的操作时,不会树上差分,打一个码量极大还容易错的的树链剖分就太吃亏了。文章来源地址https://www.toymoban.com/news/detail-533028.html

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

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

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

相关文章

  • 差分学习笔记

    1.前言 同步于 c n b l o g s cnblogs c nb l o g s 发布。 前置芝士: 基本树上操作, lca 。(用于树上差分。) 如有错误,欢迎各位大佬指出。(顺便复习一下远古算法。) 2.什么是差分 我们先给定一个数组 a a a ,长度为 n n n ,我们可以构造一个差分数组 b b b ,使得对于任意的

    2024年02月12日
    浏览(34)
  • 差分约束学习笔记

    2023.5.6 写的太烂了重新写 差分约束系统是一种特殊的 (n) 元一次不等式组,它包含 (n) 个变量 (x_{1},x_{2},...,x_{n}) 以及 (m) 个约束条件,每一个约束条件都是两个其中的变量做差构成的,形如 (x_{i}-x_{j}le c_{k}) ,其中 (1le i,jle n,ine j,1le kle m) 并且 (c_{k}) 是常数(可以

    2024年02月03日
    浏览(41)
  • 强化学习系列--时序差分学习方法(SARSA算法)

    SARSA(State-Action-Reward-State-Action)是一种强化学习算法,用于解决马尔可夫决策过程(MDP)中的问题。 SARSA算法属于基于值的强化学习算法 ,用于学习最优策略。 在SARSA算法中,智能体通过与环境进行交互来学习。它基于 当前状态、选择的动作、获得的奖励、下一个状态和下

    2024年02月11日
    浏览(36)
  • 一文带你深入了解算法笔记中的前缀与差分(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月12日
    浏览(62)
  • 强化学习:时序差分算法 TD-learning

       首先,我们考虑简单的平均估计计算: w = E [ X ] w=E[X] w = E [ X ] ,根据 RM算法 计算过程如下:   接着上面的例子,我们现在考虑一个较为复杂的问题,估计函数 v ( X ) v(X) v ( X ) 的平均值,根据 RM算法 计算过程如下:   接着上面的例子,我们现在考虑一个更复杂的

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

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

    2024年02月09日
    浏览(41)
  • C++入门: 类和对象笔记总结(上)

     C语言是 面向过程 的, 关注 的是 过程 ,分析出求解问题的步骤,通过函数调用逐步解决问题。  C++是基于 面向对象 的, 关注 的是 对象 ,将一件事情拆分成不同的对象,靠对象之间的交互完成。   C语言结构体中只能定义变量,在C++中,结构体升级成类内不仅可以定

    2024年02月07日
    浏览(41)
  • 强化学习9——免模型预测算法介绍(蒙特卡洛方法和时步差分方法)

    对于大部分情况来说,环境是未知的,也就是说状态转移概率未知,对于这种情况的算法称为 免模型预测 算法。免模型算法与环境不断交互学习,但是需要大量的运算。 蒙特卡罗方法通过重复随机抽选,之后运用统计概率此方法来从抽样结果中归纳我们想要得到的数值估计

    2024年02月02日
    浏览(44)
  • 中科院一区论文复现,改进蜣螂算法,Fuch映射+反向学习+自适应步长+随机差分变异,MATLAB代码...

    本期文章复现一篇发表于 2024年 来自中科院一区 TOP顶刊《Energy》 的改进蜣螂算法。 论文引用如下: Li Y, Sun K, Yao Q, et al. A dual-optimization wind speed forecasting model based on deep learning and improved dung beetle optimization algorithm[J]. Energy, 2024, 286: 129604. 改进的蜣螂优化算法原理如下 : 改进策

    2024年02月19日
    浏览(36)
  • 二维差分算法详解

    二维差分模板 给定一个n行m列的矩阵,下标从1开始。接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k,表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。请输出操作后的矩阵。 第一行包含三个整数n,m,q。接下来n行,每行m个整数,代表矩阵的元素。接

    2024年01月20日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包