hdu 1166 敌兵布阵（线段树单点更新，区间查询）

题意：区间和

思路：线段树

#include

#include

using namespace std;

#define MAXN 50005

int ans;

struct node{

int left,right,sum;

int mid(){

return (left+right)>>1;

}

}tree[MAXN*4];//注意范围，4倍空间

void btree(int left,int right,int rt){//建树

tree[rt].left=left;

tree[rt].right=right;

if(left==right){

scanf("%d",&tree[rt].sum);

return;

}

int mid=tree[rt].mid();

btree(left,mid,rt<<1);

btree(mid+1,right,rt<<1|1);

tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//区间里的点数=左区间+右区间

}

void query(int left,int right,int rt,int L,int R){//询问求和

if(L<=left&&right<=R){

ans+=tree[rt].sum;

return;

}

int mid=tree[rt].mid();

if(R<=mid)query(left,mid,rt<<1,L,R);//区间在左子树

else if(L>mid)query(mid+1,right,rt<<1|1,L,R);//区间在右子树

else{

query(left,mid,rt<<1,L,R);

query(mid+1,right,rt<<1|1,L,R);

}

}

void update(int left,int right,int rt,int pos,int add){//单点更新函数

if(left==right){

tree[rt].sum+=add;

return;

}

int mid=tree[rt].mid();

if(pos<=mid)update(left,mid,rt<<1,pos,add);//点在左子树

else update(mid+1,right,rt<<1|1,pos,add);//点在右子树

tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//区间和更新

}

int main(){

int t,n,a,b,i;

char str[10];

scanf("%d",&t);

for(i=1;i<=t;++i){

printf("Case %d:\n",i);

scanf("%d",&n);

btree(1,n,1);

while(~scanf("%s",str)&&str[0]!='E'){

scanf("%d%d",&a,&b);

if(str[0]=='A')update(1,n,1,a,b);

else if(str[0]=='S')update(1,n,1,a,-b);

else{

ans=0;

query(1,n,1,a,b);

printf("%d\n",ans);

}

}

}

return 0;

}

View Code

文章链接