|
|
本帖最后由 o0iver 于 2024-4-17 21:10 编辑
先做个自我介绍
大家好我是o0iver
那直接进入正题：差分是个什么 东东？？
那我们就需要先了解一下他的兄弟：前缀和
1.前缀和
前缀和通俗的定义就是一个数组前n项的和
就是sum[1]=a[1],sum[2]=a[1]+a[2],sum[3]=a[1]+a[2]+a[3]......
举个例子：
原数组（a）：1，3，4，5，7
那么前缀和sum数组就等于：1，4，8，13，20
感觉没什么用是不是？
那么我们来看看用前缀和会发生什么？
例题1：
给定数组A，现有q次询问，每次要求求出区间[l,r]的和
感觉十分的简单，每次询问for访问l到r，直接求和即可。
但是，如果数据加强呢？
已知A的长度<=10^6 q<=10^6
哦，完美超时
这时前缀和的作用就体现出来了
l到r的和其实可以转化为1到r的和减1到l的和
而通过前缀和，这两项数值都可以初始化！’
就这样，区间操作的O（n），变成了O（1）
总复杂度也降到了O（n+q）
完美！！
2.差分
为什么说差分跟前缀和是兄弟，因为差分完全是前缀和的逆运算
在前缀和中相加在差分中自然要相减！！
于是，我们就有
sum=a[i+1]-a
那么，前缀和有着区间变单点的操作，差分自然不少！！
我们先看结论
如果区间[l,r]加上一个数，那么在差分数组里：
sum[l]+n; sum[r+1]-n;
原理也很简单，那就是被减数，减数和差的关系
那我们确实将区间变为了单点，但是这又跟原数组有什么关系？
3.兄弟同心，其利断金
终极大招：差分数组的前缀和是原数组！！！！！！！！！
那么上面的问题得到了解决，在最后做一遍前缀和，所有改动便转移回了原数组
如果我们结合起来，两位兄弟对着超时就是一顿胖揍！
让我们帮他们，一起胖揍超时！！！
对了，管理员看看吧，取消验证码啊！！！！！
|
|
发表于 2024-4-17 21:09:00
置顶卡