在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 2000001
int 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 );
else
update( a,-b,1,n,1 );
}
}
return 0;
}