线段树

 1 //线段树数组静态模板
 2 
 3 
 4 #include <iostream>
 5 #include <cstdio>
 6 #define MAX 50003
 7 #define ll long long
 8 
 9 using namespace std;
10 
11 struct node
12 {
13     int w;
14     int lch, rch;
15 }Tree[4*MAX];
16 ll ans;
17 
18 void CreatTree(int l, int r, int i)
19 {
20     int mid;
21 
22     Tree[i].lch = l;
23     Tree[i].rch = r;
24     if(l == r){
25         scanf("%d",&Tree[i].w);
26         return ;
27     }
28     mid = (l+r)>>1;
29     CreatTree(l,mid,i<<1);
30     CreatTree(mid+1,r,i<<1|1);
31     Tree[i].w = Tree[i<<1].w+Tree[i<<1|1].w;
32 }
33 
34 void QueryTree(int L, int R, int l, int r, int i)
35 {
36     int mid;
37 
38     if(R<l || L>r)
39         return ;
40     if(L>=l&&R<=r){
41         ans += Tree[i].w;
42         return ;
43     }
44     mid = (L+R)>>1;
45     QueryTree(L,mid,l,r,i<<1);
46     QueryTree(mid+1,R,l,r,i<<1|1);
47 }
48 
49 void UpdateTree(int L, int R, int pos, int num, int i)
50 {
51     int mid;
52 
53     if(L == R){
54         Tree[i].w += num;
55         return ;
56     }
57     mid = (L+R)>>1;
58     if(pos<=mid)
59         UpdateTree(L,mid,pos,num,i<<1);
60     else
61         UpdateTree(mid+1,R,pos,num,i<<1|1);
62     Tree[i].w = Tree[i<<1].w+Tree[i<<1|1].w;
63 }
64 
65 int main()
66 {
67     int i, n, t, a, b, k = 0;
68     char str[10];
69 
70     scanf("%d",&t);
71     while(t-- && scanf("%d",&n)){
72         CreatTree(1,n,1);
73         printf("Case %d:
",++k);
74         while(scanf("%s",str),str[0]!='E'){
75             scanf("%d %d",&a,&b);
76             if(str[0] == 'Q'){
77                 ans = 0;
78                 QueryTree(1,n,a,b,1);
79                 printf("%lld
",ans);
80             }
81             else if(str[0] == 'A')
82                 UpdateTree(1,n,a,b,1);
83             else
84                 UpdateTree(1,n,a,-b,1);
85         }
86     }
87     return 0;
88 }

作者：blueppo
出处：http://www.cnblogs.com/Yan-C/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。