什么是差分数组?「建议收藏」

什么是差分数组?「建议收藏」问题背景如果给你一个包含5000万个元素的数组,然后会有频繁区间修改操作,那什么是频繁的区间修改操作呢?比如让第1个数到第1000万个数每个数都加上1,而且这种操作时频繁的。此时你应该怎么做?很容易想到的是,从第1个数开始遍历,一直遍历到第1000万个数,然后每个数都加上1,如果这种操作很频繁的话,那这种暴力的方法在一些实时的系统中可能就拉跨了。因此,今天的主角就出现了——差分数组。…

大家好,又见面了,我是你们的朋友全栈君。

问题背景

如果给你一个包含5000万个元素的数组,然后会有频繁区间修改操作,那什么是频繁的区间修改操作呢?比如让第1个数到第1000万个数每个数都加上1,而且这种操作时频繁的。

此时你应该怎么做?很容易想到的是,从第1个数开始遍历,一直遍历到第1000万个数,然后每个数都加上1,如果这种操作很频繁的话,那这种暴力的方法在一些实时的系统中可能就拉跨了。

因此,今天的主角就出现了——差分数组。

 

算法原型

比如我们现在有一个数组arr,arr={0,2,5,4,9,7,10,0}

什么是差分数组?「建议收藏」

那么差分数组是什么呢?其实差分数组本质上也是一个数组,我们暂且定义差分数组为d,差分数组d的大小和原来arr数组大小一样,而且d[i]=arr[i]-arr[i-1](i≠0),且d[i]=0,它的含义是什么?就是原来数组i位置上的元素和i-1位置上的元素作差,得到的值就是d[i]的值。

所以,例子中的arr数组其对应的差分数组值如下图所示。

什么是差分数组?「建议收藏」

那么构造了这么个玩意有什么用呢?难道是来浪费宝贵的内存空间的?嗯,确实是来浪费宝贵的内存了,但是却换了时间上的高效。

现在我们有这么一个区间修改操作,即在区间1~4上,所有的数值都加上3.

什么是差分数组?「建议收藏」

我们不要傻傻地遍历arr数组的[1,4]范围,然后再分别给每个值加上3,我们此时更改差分数组d即可。

显而易见,差分数组d在[2,4]范围内的值都不用改变,只需要改变差分数组位置1和位置5的值即可,即d[1]=d[1]+3,而d[5]=d[5]-3,其余不变,为什么呢?因为差分数组的定义——d[i]=arr[i]-arr[i-1]

什么是差分数组?「建议收藏」

现在,我们如何根据差分数组d来推测arr中某一个位置的值呢?

比如,此时,我们想知道arr[1]的值,我们不能直接通过arr[1]得到原来的值,因为在区间修改的操作中我们并没有修改arr的值,因此我们必须从前往后遍历递推,由于d[0]=arr[0]-0(我们定义arr[0]的前一个数为0),那么arr[0]=d[0]=0,又由于d[1]=arr[1]-arr[0]=5,那么arr[1]=5+arr[0]=5。以此类推,由于d[2]=arr[2]-arr[1]=3,所以arr[2]=3+arr[1]=8。

 

总结

可以看到,如果需要对L~R范围内所有数都进行相同的操作,我们不需要从L~R遍历arr然后在每个值上进行相同操作,只需要在差分数组d中改变L和R+1的值即可。但是在查询arr数组中某个位置的数时,却要根据差分数组从前往后递推求值。

所以,该方法适用于区间频繁修改,而且这个区间范围是比较大的,离线查询的情况。

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130341.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java线程池 面试题(精简)

    java线程池 面试题(精简)什么是线程池?线程池是一种多线程处理形式,处理过程中将任务提交到线程池,任务的执行交由线程池来管理。如果每个请求都创建一个线程去处理,那么服务器的资源很快就会被耗尽,使用线程池可以减少创建和销毁线程的次数,每个工作线程都可以被重复利用,可执行多个任务。 为什么要使用线程池?创建线程和销毁线程的花销是比较大的,这些时间有可能比处理业务的时间还要长。这样频繁的创建线程和销毁线程,再…

  • windows下安装mysql

    windows下安装mysql

    2021年11月27日
  • msdos分区是什么_msdos_partition

    msdos分区是什么_msdos_partition硬盘分区及格式化本例要求熟悉硬盘分区结构,使用fdisk分区工具在磁盘/dev/vdb上按以下要求建立分区:采用默认的msdos分区模式1、第1个分区/dev/vdb1的大小为200MiB2、第2个分区/dev/vdb2的大小为2000MiB3、第3个分区/dev/vdb3的大小为1000MiB,完成分区后4、能够配置开机自动挂载/dev/vdb2分区…

  • python基础(9)增强型赋值与使用普通赋值的区别

    python基础(9)增强型赋值与使用普通赋值的区别前言增强型赋值语句是经常被使用到的,因为从各种学习渠道中,我们能够得知i+=1的效率往往要比i=i+1更高一些(这里以+=为例,实际上增强型赋值语句不仅限于此)。所以我们会乐此不

  • jsonObject转map_json字符串转jsonobject对象

    jsonObject转map_json字符串转jsonobject对象Map转JSONObject<!–https://mvnrepository.com/artifact/com.alibaba/fastjson–><dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>1.2.59</version></depende

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号