社区讨论

树状数组的疑惑???

P3372【模板】线段树 1参与者 1已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@lyvcao3o
此快照首次捕获于
2024/07/21 17:12
2 年前
此快照最后确认于
2024/07/21 17:29
2 年前
查看原帖
树状数组的代码:
CPP
#include<bits/stdc++.h>
#define re register
#define il inline
using namespace std;
il int read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
il void write(long long x)
{
	if(x<0) {x=~(x-1); putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
const int N=1e6+6;
long long n,m,l,r,k,d,opt,a[N];
long long s1,s2,t1[N],t2[N];
il int lowbit(long long x)
{
	return x & -x;
}
il void build(long long tr[],long long i,long long k)
{
	while(i<=n) tr[i]+=k,i+=lowbit(i);
}
il long long query(long long tr[],long long x)
{
	long long ans=0;
	while(x>=1) ans+=tr[x],x-=lowbit(x);
	return ans;
}
int main()
{
	n=read(),m=read();
	for(re int i=1;i<=n;i++)
	{
		a[i]=read();
		d=a[i]-a[i-1];
		build(t1,i,d);
		build(t2,i,(i-1)*d);
	}
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			l=read(),r=read(),k=read();
			build(t1,l,k);
			build(t1,r+1,-k);
			build(t2,l,(l-1)*k);
			build(t2,r+1,-k*r);
		}
		else
		{
			l=read(),r=read();
			s1=(l-1)*query(t1,l-1)-query(t2,l-1);
			s2=r*query(t1,r)-query(t2,r);
			printf("%lld\n",s2-s1);
		}
	}
	return 0;
}
对于:
CPP
build(t2,i,(i-1)*d);
CPP
build(t2,l,(l-1)*k);
build(t2,r+1,-k*r);
之类的。
为什么都少了“1”
如:
CPP
build(t2,i,(i-1)*d);
改为
build(t2,i,i*d);

回复

3 条回复,欢迎继续交流。

正在加载回复...