简单差分入门

简单差分入门,第1张

简单差分入门

差分可以说是前缀和的逆运算了

假设给你一个数组:arr[n] = {1,4,6,-1,8,...}
给你m个 *** 作:每次 *** 作给你l,r,val,让你对数组l~r区间内的数都加上一个val

朴素的做法(单次 *** 作):
for(int i = l,i<=r;i++)
arr[i]+=val;

时间复杂度为 r-l+1
这样算下来整体的时间复杂度很大

当朴素的暴力T的时候,就需要引进差分这一算法

正如我开头说的:差分是前缀和的逆运算

我们如何理解这句话呢?
随便举一个例子:
有一个数组:arr--> 1 7 8 -19 22
我们引进一个差分数组cf

接下来请您认真看:
arr    1 7 8 -19 22
ch     1 6 1 -27 41 
引进一个前缀和sum_ch数组
sum_ch 1 7 8 -19 22

是不是神奇的发现:arr == sum_ch

所以,差分就是前缀和的逆运算
如何实现差分?
如果你理解了上面,那你绝对可以理解下面的内容了!!!

for(int i = 1;i<=n;i++)
cin>>arr[i];

arr为原数组

接下来是把arr差分化 *** 作:
----------------------
for(int i = 1;i<=n;i++)
cf[i] = arr[i] - arr[i-1]//差分是前缀和的逆运算
//arr[0] = cf[0] = 0(开全局变量,初始化为全0)
----------------------

接下来是某些操作了,还是按文章最开始的,给你l,r,val,让你对区间l~r数组中的数加上一个val
----------------------
cf[l] += val;
cf[r+1] += val;
就是如此的简单
----------------------
接下来就是输出操作后的数据了
----------------------
int sum = 0;
for(int i = 1;i<=n;i++)
{    
    sum+=cf[i];
    cout< 

接下来是一道非常板的题:

797. 差分 - AcWing题库

AC代码如下:

#include
#include
using namespace std;
const int N = 1e5+9;
int s[N],cf[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		cin>>s[i];
		cf[i] = s[i]-s[i-1];
	}
	while(m--)
	{
		int l,r,vis;
		cin>>l>>r>>vis;
		cf[l]+=vis;
		cf[r+1]-=vis;	
	}
	int ans = 0;
	for(int i = 1;i<=n;i++)
	{
		ans+=cf[i];
		cout<

最后,感谢您的阅读!!!

 志在顶峰的人,决不会因留恋半山腰的奇花异草而停止攀登的步伐。——高尔基

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5711463.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存