一维前缀和
一般用于求某一区间上数组的和
` ** //一般用于求数组区间和
for(int i=1;i<=n;i++) scanf("%d",&a[i]); //原数组
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; //构造前缀和数组
printf("%d\n",s[r]-s[l-1]); //求数组区间和`**
一维差分
一般用于给某一段区间各项都加减常数c
`void insert(int l,int r,int c) //insert函数最重要
{ //核心
b[l]+=c;
b[r+1]-=c;
}
for(int i=1;i<=n;i++) scanf("%d",&a[i]); //原数组a
for(int i=1;i<=n;i++) insert(i,i,a[i]); //通过insert函数构造差分数组b[i]
while(m--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c); //通过insert函数对差分数组操作
}
for(int i=1;i<=n;i++) b[i]+=b[i-1]; //将b[i]自身进行前缀和运算,更新为a[i]`
第二种模版
` for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++) b[i] = a[i] - a[i-1];
int l,r,c;
cin>>l>>r>>c;
//关键步骤
b[l] += c;
b[r+1] -= c;
for(int i = 1;i<=n;i++)
{
a[i] = b[i] +a[i-1];
cout<<a[i]<<" ";
} `