首页 > 代码库 > hdu 1166 敌兵布阵（单点更新，区间查询）
hdu 1166 敌兵布阵（单点更新，区间查询）
题意：
N个工兵营地。工兵营地里的人数分别为：a1,a2,....aN
Add i,j：第i个工兵营地里增加j人
Sub i,j：第i个工兵营地里减少j人
Query i,j：查询第i个第j个工兵营地共有多少人
思路：
线段树、树状数组都可以做，看代码
代码：
线段树：
const int maxn = 50005;int sum[maxn<<2];void PushUp(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt){ if(l==r){ scanf("%d",&sum[rt]); return; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}void update(int p,int add,int l,int r,int rt){ if(l==r){ sum[rt] += add; return; } int m = (l + r) >> 1; if(p <= m) update(p,add,lson); else update(p,add,rson); PushUp(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l && r<=R){ return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if(L <= m) ret += query(L,R,lson); if(R > m) ret += query(L,R,rson); return ret;}int main(){ int T,n; scanf("%d",&T); for(int t=1;t<=T;++t){ printf("Case %d:\n",t); scanf("%d",&n); build(1,n,1); char op[10]; while(scanf("%s",op)){ if(op[0] == ‘E‘) break; int a, b; scanf("%d%d",&a,&b); if(op[0] == ‘A‘) update(a,b,1,n,1); else if(op[0] == ‘S‘) update(a,-b,1,n,1); else if(op[0] == ‘Q‘) printf("%d\n",query(a,b,1,n,1)); } }}
树状数组：
int n;int a[50005];int C[50005];void init(){ rep(i,1,n){ C[i]=0; for(int j=i-lowbit(i)+1;j<=i;j++){ C[i]+=a[j]; } }}void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)){ C[i]+=y; }}int calc(int x){ if(x==0) return 0; int ans=0; for(int i=x;i>0;i-=lowbit(i)) ans+=C[i]; return ans;}int query(int x,int y){ return calc(y)-calc(x-1);}int main(){ int T; cin>>T; rep(t,1,T){ scanf("%d",&n); rep(i,1,n){ scanf("%d",&a[i]); } init(); printf("Case %d:\n",t); char ope[10]; while(1){ scanf("%s",ope); if(ope[0]==‘E‘) break; int x,y; if(ope[0]==‘A‘){ scanf("%d%d",&x,&y); add(x,y); } else if(ope[0]==‘S‘){ scanf("%d%d",&x,&y); add(x,-y); } else{ scanf("%d%d",&x,&y); int ans=query(x,y); printf("%d\n",ans); } } } return 0;}
hdu 1166 敌兵布阵（单点更新，区间查询）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。