简单差分入门

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

假设给你一个数组：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