Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 36121 Accepted
Submission(s): 15282
1 //328MS 1984K 1515 B G++ 2 /* 3 4 模板题. 5 6 */ 7 #include<stdio.h> 8 #include<string.h> 9 #define N 50005 10 int p[N]; 11 struct node{ 12 int l,r; 13 int num; 14 }tree[4*N]; 15 void build(int l,int r,int id) //构图 16 { 17 tree[id].l=l; 18 tree[id].r=r; 19 if(l==r){ 20 tree[id].num=p[l];return; 21 } 22 int mid=(l+r)>>1; 23 build(l,mid,2*id); 24 build(mid+1,r,2*id+1); 25 tree[id].num=tree[2*id].num+tree[2*id+1].num; 26 } 27 void update(int x,int change,int id) //更新 28 { 29 if(tree[id].l==x && tree[id].r==x){ 30 tree[id].num+=change;return; 31 } 32 int mid=(tree[id].l+tree[id].r)>>1; 33 if(x<=mid) update(x,change,2*id); 34 else update(x,change,2*id+1); 35 tree[id].num=tree[2*id].num+tree[2*id+1].num; 36 } 37 int query(int l,int r,int id) //查询 38 { 39 if(tree[id].l>=l && tree[id].r<=r){ 40 return tree[id].num; 41 } 42 int mid=(tree[id].l+tree[id].r)>>1; 43 if(mid<l) return query(l,r,2*id+1); 44 else if(mid>=r) return query(l,r,2*id); 45 else return query(l,mid,2*id)+query(mid+1,r,2*id+1); 46 } 47 int main(void) 48 { 49 int t,n,k=1; 50 int a,b; 51 char op[10]; 52 scanf("%d",&t); 53 while(t--) 54 { 55 scanf("%d",&n); 56 for(int i=1;i<=n;i++) scanf("%d",&p[i]); 57 build(1,n,1); 58 printf("Case %d:\n",k++); 59 while(scanf("%s",op)){ 60 if(strcmp(op,"End")==0) break; 61 scanf("%d%d",&a,&b); 62 if(op[0]==‘A‘) update(a,b,1); 63 else if(op[0]==‘S‘) update(a,-b,1); 64 else printf("%d\n",query(a,b,1)); 65 } 66 } 67 return 0; 68 }
hdu 1166 敌兵布阵 (线段树),布布扣,bubuko.com
原文:http://www.cnblogs.com/GO-NO-1/p/3627705.html