社区讨论

求助!有大佬能帮我看下哪里出问题了吗?

P3368【模板】树状数组 2参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6znd4l
此快照首次捕获于
2025/11/20 13:26
4 个月前
此快照最后确认于
2025/11/20 13:26
4 个月前
查看原帖
我的我区间修改+区间查询树状数组不知道哪里出问题了,求大佬帮忙看一下。
码风难看请勿喷
CPP
#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 条回复,欢迎继续交流。

正在加载回复...