改了一晚上线段树模板,帮帮我吧
查看原帖
改了一晚上线段树模板,帮帮我吧
180453
wangyansong楼主2020/11/30 20:12
#include<bits/stdc++.h>
using namespace std;
const int M=100005;
struct node{
	int le,ri,s;
}t[M*4];
int n,w;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}
void build(int l,int r,int x)
{
	t[x].le = l;
	t[x].ri = r;
	t[x].s = 0;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
}
void jia(int x,int dis,int k)
{
    if(t[x].le == t[x].ri ) {
    	t[x].s +=k;
    	 return ;
	}
	int mid=(t[x].le + t[x].ri )/2;
	if(dis<=mid ) jia(x*2,dis,k);
    else jia(x*2+1,dis,k);
    t[x].s = t[x*2+1].s + t[x*2].s ;
}
int se(int x,int l,int r)
{
	if(t[x].le >=l&&t[x].ri <=r){
		return t[x].s ;
	}
	int mid=(t[x].le +t[x].ri )/2;
	int ans=0;
	if(mid>=l) ans+=se(x*2,l,r);
	if(mid<r) ans+= se(x*2+1,l,r);
	return ans;
}
int main()
{
	n=read(),w=read();
	build(1,n,1);
	while(w--){
		char x;
		int a,b;
		scanf(" %c ",&x);
		a=read(),b=read();
		if(x=='x'){
			jia(1,a,b);
		}
		else {
			cout<<se(1,a,b)<<endl;
		}
	}
	return 0;
}
2020/11/30 20:12
加载中...