题目描述
1.为什么加减常数c为1?
因为最后是对数组进行1的增改,初始的数组即为差(原始)
2.为什么要使用差分?
后面;
3.改变最前面和最后面即”l,r”该怎么取值?
1.对于标准的差分模版,会直接给出l,r,c;
2.而,如果给出了其中两个则可以求出全部
4.为什么要用memset()将数组清空?
怕之前的数组太大,即使覆盖也会有杂余
5.与普通的差分有什么不同?
1.不需要求差,直接为最原始:以后可以看看,它给出了什么,没有给a则不需要求差
6.平常我们写差分时,应注意的点还有差分的核心思路是什么?
注意数组的下标,l和r-1;如果从一开始读入数组,且小区间为x,则开始区间为i-x+1(i为此时数组的长度)
核心:求差,加减,求和;
样例
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n;
int a[200001];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(a,0,(n+1)*4);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
x=min(x,i);
int l=i-x+1,r=i;
a[l]++,a[r+1]--;
}
for(int i=1;i<=n;i++)a[i]+=a[i-1];
for(int i=1;i<=n;i++)printf("%d ",!!a[i]);
printf("\n");
}
return 0;
}
用这个会更加清楚:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n;
int a[200001];
void chafen(int l,int r)
{
a[l]+=1;
a[r+1]-=1;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(a,0,(n+1)*4);//作用为清除一个长度为(n+1)*4字节的数组(长度是按字节算的)
//因为要进行t次,而a不能重复使用,不如清除一个干净数组,用于储存a;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);//因为要对从后向前数x个数进行加减1的操作,自然x决定了开始加减数组//区间的起始位置
x=min(x,i);//我们已将知道,x和i的关系决定着加减数组区间的位置,由题意可知x的长度//可能会超出所插入的0的个数,所以要看看具体的区间长度
chafen(i-x+1,i);//so important!
}
for(int i=1;i<=n;i++)a[i]+=a[i-1];
for(int i=1;i<=n;i++)printf("%d ",!!a[i]);//最后的值也不一定要非得是0或者为1,差分的值也不为一定为0或者1,此题表示的//是这个位置的数被操作了几次
printf("\n");
}
return 0;
}
差分核心思想是什么:
(差分) $O(n^log(n))
注意事项是什么?
1.为什么用差分?
时间复杂度会大大减少;
要求一个区间整个数组都要加上一个常数c,且有很多次,比较麻烦且如果数据n比较大时,时间复杂度会很大,n的好几次方,不如就在数列的一个区间的第一个数和最后一个数进行操作,最后把总的n遍历一遍以求加好c的整个数组;
2.insert(i,i,a[i])是用来求什么的?为什么要有这么一步操作?
1.来求b[i]=a[i]-a[i-1],将其求出来之后,在某一段区间的第一位和最后一位进行操作,进行m次操作后,再进行for循环,求出总的数组;
2.因为这是在数组整体加上或者减去c操作之前,必经的步骤,(差分)就是这么来的,先差再说
为了后面总体的for循环;
3.一维差分的具体步骤:
1.判断能否用差分:是否要进行q次询问,是否要对某一区间进行增减一个常数,(是否有原始数组),以及要判断常数c,是否为一常数,或者为某一数组;
2.将差分函数表达出来:
void chafen(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
3.判断是否需要(例如本题不需要将差分数组b算出来,判断好哪个是a,哪个是b,哪个是c)将差先算出来,b[i]=a[i]-a[i-1];如果需要则
for(int i=1;i<=n;i)
chafen(i,i,a[i]);
4.进行q次操作,计算将差分数组进行加减常数c
while(q–)
{
int l,r,c;
scanf(“%d %d %d”,&l,&r,&c);
chafen(l,r,c);
}
5.进行求和运算,将所有的都遍历一遍:
for(int i=1;i<=n;i)
b[i]+=b[i-1];//求出最终值;
C++ 代码
差分的基本模板:
#include<iostream>
#include<algorithm>
using namespace std;
int n,q;
const int N=100001;
int a[N],b[N];
void chafen(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
chsfen(i,i,a[i]);//求得差;
}
//对某一段数进行加上或者减去常数;
while(q--)
{
int l,int r,c;
scanf("%d%d%d",&l,&r,&c);
chafen(l,r,c);
}
for(int i=1;i<=n;i++)b[i]+=b[i-1];
for(int i=1;i<=n;i++)printf("%d ",b[i]);
printf("\n");
return 0;
}
差分一般用于解决哪几种问题?
待我做做题|
blablabla
时间复杂度
参考文献
C++ 代码
blablabla