博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
差分数组
阅读量:5835 次
发布时间:2019-06-18

本文共 557 字,大约阅读时间需要 1 分钟。

先来看一道例题,给定一个长度为n(n≤107)的数列{a1,a2,…,an},初始状态为0m(m≤107)次操作,每次可以选择一个区间[l,r],使下标在这个区间内的数都加k或者都减k,求这m次操作每一个数的最后结果。(原创?)

O(n×m)暴力应该很好想,对叭~

但是呢?数据范围就是这样的不友好,怎么办?


 

这时候就要引入一个新的概念:差分数组

首先我们先来定义一下这个数组:

对于给定的数列A,它的差分数组B定义为:B[1]=A[1],B[i]=A[i]-A[i-1](2≤i≤n)

容易发现“前缀和数组”和“差分数组”存在着互逆运算关系,在此就不再赘述,感兴趣的大佬可以自行研究。

那么,把序列A的区间[l,r]k(即把Al,Al+1,…,Ar都加上k),其差分数组B的变化为Bl加k,Br+1k,其他位置不变。

可以感性的理解为,第l位比第l-1大了k,而因为加上了这个k所以第r+1位会比第r位小k,所以需要减去。

统计答案时,我们只需要把这个差分数组相加即可,因为差分数组的前缀和数组即为原序列(一定注意B[1]=A[1])。

每次操作时间复杂度O(1)

总时间复杂度O(n+m)


 

rp++

转载于:https://www.cnblogs.com/wzc521/p/11032190.html

你可能感兴趣的文章
关于数据分析思路的4点心得
查看>>
Memcached安装与配置
查看>>
美团数据仓库的演进
查看>>
SAP被评为“大数据”预测分析领军企业
查看>>
联想企业网盘张跃华:让文件创造业务价值
查看>>
记录一次蚂蚁金服前端电话面试
查看>>
直播源码开发视频直播平台,不得不了解的流程
查看>>
Ubuntu上的pycrypto给出了编译器错误
查看>>
聊聊flink的RestClientConfiguration
查看>>
在CentOS上搭建git仓库服务器以及mac端进行克隆和提交到远程git仓库
查看>>
測試文章
查看>>
Flex很难?一文就足够了
查看>>
【BATJ面试必会】JAVA面试到底需要掌握什么?【上】
查看>>
CollabNet_Subversion小结
查看>>
mysql定时备份自动上传
查看>>
17岁时少年决定把海洋洗干净,现在21岁的他做到了
查看>>
linux 启动oracle
查看>>
《写给大忙人看的java se 8》笔记
查看>>
倒计时:计算时间差
查看>>
Linux/windows P2V VMWare ESXi
查看>>