在Alibaba上碰到了中级的线段树问题，另外在队内集训的时候做2010年的多校联合的题时，遇到了两道线段树。
但是无奈的我只会树状数组。如果用树状数组来段更新，简直是以卵击石嘛~
接连受打击，无奈之下只好拜读了下Roba，NOS的博客，他们的教学博客写得很好。
简直是膜拜了~~~
鄙人无奈的弱菜啊~~
线段树基于二叉查询数，通过手动judge可以知道其美妙的结构~
网络上很多的树形图都是错的。
(1,6) 1
/ \ / \
(1,3) (4,6) 2 3
/ \ / \ / \ / \
(1,2) (3,3) ( 4,5) (6,6) 4 5 6 7
/ \ / \ / \ / \
(1,1) (2,2) (4,4) (5,5) 8 9 12 13
上面左图数线段树，右图是每个节点在一维数组中对应的标号。
学过数据结构的同学应该知道二叉树的原理
同样在线段树中也能这样。
每个根节点的左子树标号=当前根节点标号<<1;
每个根节点的右子树标号=当前根节点标号<<1|1;
对于构建二叉树用递归就行了。
稍微理解一下二叉树，对于线段树就很好写了。
当然我写得是最最简单最最基础的线段树，一句话 弱爆了！
#include<stdio.h>
#include<string.h>
#define MAXN 2000001int sum[MAXN];
void PushUp( int root ){sum[root]=sum[root<<1]+sum[root<<1|1];
}void build( int l,int r,int root )
{if( l==r ){scanf( "%d",&sum[root] );return ;}int m=(l+r)/2;build( l,m,root<<1 );build( m+1,r,root<<1|1 );PushUp(root);
}void update( int at,int value,int L,int R,int root )
{if( L==R ){sum[root]+=value;return ;}int m=(L+R)/2;if( at<=m )update(at,value,L,m,root<<1 );else update( at,value,m+1,R,root<<1|1 );PushUp( root );
}int query( int l,int r,int L,int R,int root )
{int res=0;if( l<=L && R<=r )return sum[root];int m=(L+R)/2;if( l<=m )res+=query( l,r,L,m,root<<1 );if( m<r )res+=query( l,r,m+1,R,root<<1|1 );return res;
}int main()
{int loop,a,b,c;char com[100];int index=1;scanf( "%d",&loop );while( loop-- ){int i,j,n;scanf( "%d",&n );build(1,n,1);printf( "Case %d:\n",index++ );while( scanf( "%s",com ) ){if( com[0]=='E' )break;scanf( "%d%d",&a,&b );if( com[0]=='Q' )printf( "%d\n",query(a,b,1,n,1) );else if( com[0]=='A' )update( a,b,1,n,1 );elseupdate( a,-b,1,n,1 );}}return 0;
}