线段树全RE.....
  • 板块P2068 统计和
  • 楼主wys0929
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/9/26 21:29
  • 上次更新2023/11/2 17:57:24
查看原帖
线段树全RE.....
592032
wys0929楼主2023/9/26 21:29
#include<bits/stdc++.h>
using namespace std;
long long n,w;
long long a[1000005],he[5000020];
long long ls(long long x){//左子树 
	return x*2;
}
long long rs(long long x){//右子树 
	return x*2+1;
}
long long pushup(long long rt){//上推和值 
	he[rt]=he[ls(rt)]+he[rs(rt)];
}
void update(long long rt,long long l,long long r,long long p,long long k){//单点更新 
	long long mid=(l+r)/2;
	if(l==r){
		he[rt]+=k;
		return;
	}
	else{
		if(p<=mid){
			update(ls(rt),l,mid,p,k);
		}
		else{
			update(rs(rt),mid+1,r,p,k); 
		}
		pushup(rt);
	}
} 
long long query(long long rt,long long l,long long r,long long qx,long long qy){//区间查询 
	long long ans=0;
	if(qx<=l&&qy>=r){
		return he[rt];
	}
	long long mid=(l+r)/2;
	if(qx<=mid)ans+=query(ls(rt),l,mid,qx,qy);
	if(qy>mid)ans+=query(rs(rt),mid+1,r,qx,qy);
	return ans;
} 
int main(){
	cin>>n>>w;
	for(long long i=1;i<=w;i++){
		char x;
		long long s,b;
		cin>>x>>s>>b;
		if(x=='x'){
			update(1,1,n,s,b);
		}
		else{
			cout<<query(1,1,n,s,b)<<'\n';
		}
	} 
}
2023/9/26 21:29
加载中...