算法基础之差分和前缀和

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

差分

差分介绍

结论:差分是前缀和的逆运算

举例

一维差分
//一维前缀和 a[i]部分就是一维差分数组
s[i] = s[i-1]+a[i];
//一维差分 
a[i] = s[i]-s[i-1];

二维差分
//二维前缀和 a[i][j]部分就是一维差分数组
s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
//二维差分
a[i][j] = s[i][j]-s[i-1][j]-s[i][j-1]+s[i-1][j-1];

差分用法

用在一维子区间里的数都增减一个固定值,把对于区间内每个数的操作转换为对于差分数组中的端点的操作,时间复杂度降为o(1)。

用在二维子矩阵里的数都增减一个固定值,把对于子矩阵的每个数的操作转换为对应差分二维数组各个端点的操作。

总体思想就是在需要处理的区间范围内增减一个固定值,在影响到的其他范围内需要恢复,即相反操作。

举例

一维差分

差分数组在左端点增加c之后,会影响以其开始前缀和都增加c。所以为了确保只有LR这段增加c,需要从R+1开始减少c,即差分数组在R+1处减去c。

b[l]+=c;
b[r+1]-=c;

算法基础之差分和前缀和,算法基础,算法,c++,数据结构

二维差分

在 二维差分数组(x1,y1)增加会使得以(x1,y1)(n,m)范围内所有的数都增加c。所以为了确保只有(x1,y1)-(x2,y2)范围内数值增加c,则需要消除绿色部分的影响,做逆向操作。

b[x1][y1] += c;
b[x1][y2+1] -= c; //逆操作1
b[x2+1][y1] -= c;//逆操作2
b[x2+1][y2+1] +=c;//这块区域在逆操作1和2中减了两次,所以需要加上一次

算法基础之差分和前缀和,算法基础,算法,c++,数据结构

差分使用技巧

朴素思维

正常想法会先接收初始数组的输入,然后再计算每个差分数组。

一维数组
for(int i=1;i<=n;i++){
	cin >> a[i];
	b[i] = a[i]-a[i-1];
}
while(q--){
    int l,r,c;
    cin >>l>>r>>c;
    b[l] +=c;
    b[r+1] -=c;
}
二维数组
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin >>a[i][j];
		b[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
	}

while(q--){
    int x1,y1,x2,y2,c;
    cin >>x1>>y1>>x2>>y2>>c;
    
    b[x1][y1] +=c;
    b[x1][y2+1] -=c;
    b[x2+1][y1] -=c;
    b[x2+1][y2+1] +=c;
}
	

简化思维

把全0当做初始数组,即初始的差分数组都是0,。接收输入的时候就执行差分数组的修改操作,当接收问询的时候 也当做是执行差分数组的修改操作。这样就不用额外计算差分数组的具体值。

一维数组

void insert(int l,int r,int c){
	b[l] +=c;
    b[r+1] -=c;
}
for(int i=1;i<=n;i++){
	cin >> a[i];
	insert(i,i,a[i]); //起始点i到结束点i,只有一个元素的区间
}
while(q--){
    int l,r,c;
    cin >>l>>r>>c;
    insert(l,r,c);c
}
二维数组
void insert(int x1,int y1,int x2,int y2,int c){
	 b[x1][y1] +=c;
    b[x1][y2+1] -=c;
    b[x2+1][y1] -=c;
    b[x2+1][y2+1] +=c;
}
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin >>a[i][j];
		insert(i,j,i,j,a[i][j]); //起始点(i,j)到(i,j)只有一个元素的矩阵
	}

while(q--){
    int x1,y1,x2,y2,c;
    cin >>x1>>y1>>x2>>y2>>c;
    insert(x1,y1,x2,y2,c);
   
}

前缀和

前缀和分类

前缀和大体可以分为一维数组的前缀和和二维数组的前缀和。二维数组主要适用场景是矩阵相关的运算。

一维数组的前缀和

s[i] =s[i-1]+a[i]

二维数组的前缀和

总体思想:先计算以(1,1)为起始点 到各个点的区域总和,再用差值法计算给定的起始点到终点的区域总和

计算以(1,1)起始点的区域的总和

//计算s[i][j]的值
s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

算法基础之差分和前缀和,算法基础,算法,c++,数据结构

计算给定区域的总和

//计算(x1,y1)到(x2,y2)区域的值
s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; //中间-1的部分都是起始点(x1,y1)的坐标

算法基础之差分和前缀和,算法基础,算法,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-730615.html

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

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

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

相关文章

  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(51)
  • 【数据结构基础】树 - 前缀树(Trie Tree)

    Trie,又称字典树、单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的

    2024年02月07日
    浏览(45)
  • 【有营养的算法笔记】基础算法 —— 推导证明前缀和与差分

    👑作者主页:@安 度 因 🏠学习社区:StackFrame 📖专栏链接:有营养的算法笔记 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 Hello,小伙伴们,好几天没有更新了,今天更了一篇比较“硬核的文章”。 主要内容为前缀和与差分算法的推导证明和代码实现。这篇文章博主还是画

    2024年01月21日
    浏览(51)
  • 【尚硅谷】数据结构和算法——前缀、中缀、后缀表达式规则

    跟着B站的尚硅谷学习数据结构与算法,语言为java,目前是第七个代码内容——前缀、中缀、后缀表达式 课程传送门:尚硅谷——前缀、中缀、后缀表达式 1)前缀表达式又称波兰式, 前缀表达式 的运算符位于操作符之前。 2)举例说明:(3+4)*5-6 对应的前缀表达式就是 - *

    2024年02月03日
    浏览(60)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(47)
  • 算法基础学习笔记——④前缀和\差分\双指针\位运算

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨前缀和 ✨一维前缀和 🍓一维前缀和模板: ✨二维前缀和 🍓二位前缀和模板: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 原i:a[1] a[2] a[3] …a[n] 前缀和:s[i]=a[1]+a[2]+…+a[i] s[0]=0(方便处理

    2024年02月08日
    浏览(48)
  • 数据结构--》从数据结构开始,打好算法基础

    目录 数据结构的基本概念 数据结构的三要素 算法的基本概念 数据结构的基本概念         在学习某个知识之前,我们是否都有问过自己我们到底在学习的目的是什么?学习数据结构也一样,我们学习数据结构 主要是为了 用程序把现实世界的问题信息化;用计算机高效

    2024年02月09日
    浏览(53)
  • 前缀和&差分算法(Python版)

    前缀和与差分是常用的区间优化方式,其中前缀和数组可以将区间查询的时间复杂度降为常数,而差分数组则可以将区间修改的时间复杂度降为常数。 前缀和知识点简单易理解,但出题难度较大,需要根据题意挖掘出潜在的前缀和关系,建立辅助数组求解问题。 (1)一维前

    2024年04月17日
    浏览(53)
  • 【算法】—前缀和与差分详解

     前缀和指一个数组的某下标之前的所有数组元素的和( 即数列的前n项求和 ),前缀和是一种重要的 预处理 ,能够降低算法的时间复杂度,可以快速地求出某一段的和,对于处理区间之间的问题是往往十分高效 相比较其他算法而言, 前缀和更像是一种解题的技巧,一种优

    2024年02月04日
    浏览(55)
  • 【算法基础】数据结构

    826. 单链表 - AcWing题库 827. 双链表 - AcWing题库 828. 模拟栈 - AcWing题库 3302. 表达式求值 - AcWing题库 遍历输入的操作 如果是数字就存入num的堆栈 (同时注意123,2123这种长数字要一次性存入) 如果是(  直接存入op的堆栈 如果是  )就一直运算,直到遇到( 如果是操作符(如

    2024年02月12日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包