树状数组怎么维护d[i]*i的前缀和?
  • 板块P2357 守墓人
  • 楼主若素
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/7/26 11:33
  • 上次更新2023/11/4 13:17:16
查看原帖
树状数组怎么维护d[i]*i的前缀和?
85897
若素楼主2021/7/26 11:33

1、在用树状数组维护d[i]*i的前缀和时,为什么只需要在L处加上Lx,在R+1处减去(R+1)x?以L+1处元素为例,它的前缀和增加了Lx,但实际上应该增加Lx+(L+1)x,求大佬解惑

2、以下是我这题的模板,求大佬帮忙看看错误在哪里

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll a[N],c1[N],c2[N],d[N],mai,h,n,m,e,f,g,ans,k,val;
inline ll read(){
	ll ss=0;char cc=getchar();bool ff=true;
	for(cc;!isdigit(cc);cc=getchar()) if(cc=='-') ff=false;
	for(cc;isdigit(cc);cc=getchar()) ss=ss*10+cc-'0';
	return ff?ss:-ss;
}
int lowbit(int x){
	return x&-x;
}
void add(int x,ll y){
	val=x*y;
	for(x;x<=n;x+=lowbit(x)){
		c1[x]+=y;c2[x]+=val;
	}
}
void init(){
	for(int i=1;i<=n;++i) d[i]=a[i]-a[i-1];
	for(int i=1;i<=n;++i){
		k=lowbit(i);
		c1[i]=d[i];c2[i]=d[i]*i;
		for(int j=1;j<k;j<<=1){
			c1[i]+=c1[i-j];c2[i]+=c2[i-j];
		}
	}
}
ll ask(ll x){
	ans=0;
	for(ll i=x;i;i-=lowbit(i)) ans+=(x+1)*c1[i]-c2[i];
	return ans;
}
ll query(ll l,ll r){
	return ask(r)-ask(l-1);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	init();
	while(m--){
		e=read();
		if(e==1){
			f=read();g=read();h=read();
			add(f,h);add(g+1,-h);
			if(f==1) mai+=h;
		}
		else if(e==2) mai+=read();
		else if(e==3) mai-=read();
		else if(e==4) printf("%lld\n",query(read(),read()));
		else printf("%lld\n",mai);
	}
	return 0;
}
2021/7/26 11:33
加载中...