题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
我的第一道线段树啊。。。好久以前就想看线段树了，但因为各种各样的原因就一直拖着没去看，今天就突然想看了，然后首选的当然是HH大神的博客了。。。orz,给跪了。。。
一开始，我不明白到底是怎么来建树的。。。debug了好久，终于恍然大悟了。。。一晚上，总算没有白忙乎啊！！！
然后输入的时候每次都是输入叶子结点的value,在Updata就行了，然后要把叶子结点的信息更新到父结点，就要用Push_Up。。。这样就建好一颗线段树了，如果要对每个标号下的叶子结点进行修改，就相当于是单点更新就行了，然后再Push_Up更新父结点信息就行了；如果是求某一段区间的和，那么就要用到Query。。。不多说了，直接贴代码了。。。
View Code
1 #include<iostream> 2 const int MAXN=55555; 3 using namespace std; 4 int sum[MAXN<<2];//一般来说节点数要开MAXN的4倍 5 6 //是把当前结点的信息更新到父结点，父结点的为左孩子结点的值与右孩子结点的值的和 7 void Push_Up(int rt){ 8 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 9 } 10 11 //创建线段树 12 void Build(int l,int r,int rt){ 13 if(l==r){ 14 scanf("%d",&sum[rt]); 15 return ; 16 } 17 int m=(l+r)>>1; 18 Build(l,m,rt<<1); 19 Build(m+1,r,rt<<1|1); 20 Push_Up(rt); 21 } 22 23 //单点更新（相当于是从底层往上一层一层更新） 24 void Updata(int p,int add,int l,int r,int rt){ 25 if(l==r){ 26 sum[rt]+=add; 27 return ; 28 } 29 int m=(l+r)>>1; 30 if(p<=m)Updata(p,add,l,m,rt<<1); 31 else Updata(p,add,m+1,r,rt<<1|1); 32 Push_Up(rt); 33 } 34 35 //区间求和 36 int Query(int L,int R,int l,int r,int rt){ 37 //刚好落在这个区间 38 if(L<=l&&r<=R){ 39 return sum[rt]; 40 } 41 int m=(l+r)>>1; 42 int ret=0; 43 if(L<=m)ret+=Query(L,R,l,m,rt<<1); 44 if(R>m)ret+=Query(L,R,m+1,r,rt<<1|1); 45 return ret; 46 } 47 48 49 int main(){ 50 int _case,k=1; 51 scanf("%d",&_case); 52 while(_case--){ 53 int n; 54 scanf("%d",&n); 55 Build(1,n,1); 56 printf("Case %d:\n",k++); 57 while(1) 58 { 59 char str[100]; 60 scanf("%s",str); 61 if(str[0]=='E')break; 62 int b,c; 63 scanf("%d%d",&b,&c); 64 if(str[0]=='Q'){ 65 printf("%d\n",Query(b,c,1,n,1)); 66 }else if(str[0]=='A'){ 67 Updata(b,c,1,n,1); 68 }else if(str[0]=='S'){ 69 Updata(b,-c,1,n,1); 70 } 71 } 72 } 73 return 0; 74 }