社区讨论
求助!有大佬能帮我看下哪里出问题了吗?
P3368【模板】树状数组 2参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6znd4l
- 此快照首次捕获于
- 2025/11/20 13:26 4 个月前
- 此快照最后确认于
- 2025/11/20 13:26 4 个月前
我的我区间修改+区间查询树状数组不知道哪里出问题了,求大佬帮忙看一下。
#include<bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
using namespace std;
int n,m;
int a[1000010];//a存前缀和
int c[1000010];//c1与c2两个树状数组
//c1维护c数组的和,c2维护c[i]*i的和
int c1[1000010],c2[1000010];
int add(int *apk,int x,int k)
{
while(x<=n)
{
apk[x]+=k;
x+=lowbit(x);
}
return 0;
}
int md(int l,int r,int x)
{
add(c1,l,x);
add(c1,r+1,-x);
add(c2,l,x*l);
add(c2,r+1,-x*(r+1));
return 0;
}
int getsum(int *apk,int x)
{
int sum=0;
while(x!=0)
{
sum+=apk[x];
x-=lowbit(x);
}
return sum;
}
int qur(int l,int r)
{
return a[r]+r*getsum(c1,r)-getsum(c2,r)-(a[l-1]+l*getsum(c1,l-1)-getsum(c2,l-1));
}
int main()
{
int i,last=0,now;
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&now);
a[i]+=now;
add(c,i,now-last);
last=now;
c1[i]+=c[i];
c2[i]+=c1[i]*i;
}
for(i=1;i<=m;i++)
{
int o,x,y,z;
scanf("%d",&o);
if(o==1)
{
scanf("%d%d%d",&x,&y,&z);
md(x,y,z);
}
else if(o==2)
{
scanf("%d%d",&x,&y);
printf("%d\n",qur(x,y));
}
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...