刚开始接触线段树，不得不说，每次接触到一个新的数据结构，都会是一场头脑风暴的“盛宴”。希望我能继续痛苦并快乐着学下去。我相信，有各路大神的博客相助，我还是能坚持下去的。
这个题目是HDU的1166，只是题意改了一下（把士兵改为花的美观值了），实际上是一模一样的。用模拟的话妥妥的超时，别问我怎么知道的，哎，心累。线段树，我觉得最经典的也是最难的地方就是数据的更新，当你每次进行修改操作时，你要改动那个节点的所有父节点上的值，这点尤其重要！
关于线段树的一个重要的关系：如果上个节点是[a,b],则它的左子树为[a,(a+b)/2],右子树为[(a+b)/2+1,b]。顺便一提的就是线段树上的每个节点都是线段。听起来挺有趣的哈......
大致题意是这样的：有四种操作，它们的形式是这样的：（i和j为正整数）
1.Add i j, 表示第i个数增加j(j<=30)
2.Sub i j, 表示第i个数减少j(j<=30)
3.Query i j, i<=j，表示询问第i个数到第j的数的和
4.End, 表示结束，这条命令在每组数据最后出现
下面给出样例输入输出：（第一个数T表示有T数，第二个数N表示有个数，每次遇到询问Query时输出一下结果）
Sample Input
1
9
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End
Sample Output（对于每i组，首先输出一个Case i:）
Case 1:
13
30
50
30
50
下面就贴代码吧，老规矩，思路在注释里。
#include<stdio.h>
#include<string.h> #define SIZE 50010//存储N个花盆的美观值
#define MAXN 150000//存储树节点 int T,N,ans,x,y,n[SIZE];
char p[];
tree t[MAXN]; struct tree
{
int a,b,s;//线段树每个节点的左端点a，右端点b，以及[a,b]的总美观值
}; void Init(int x,int y,int z)//构造线段树
{
if(t[z].a==t[z].b)//叶子节点（[1,1],[2,2]...）的形式
t[z].s=n[y];
else
{
Init(x,(x+y)/,*z);//构造左子树
Init((x+y)/+,y,*z+);//构造右子树
t[z].s=t[*z].s+t[*z+].s;//父节点上的总美观值=两子树美观值的和
}
}
//变为2*z的原因是：一个二叉树第n层的第一个节点的编号是第（n-1）层的第一个节点的两倍（1,2,4,8....） void Add(int x,int y,int z)//区间修改Add
{
t[z].s+=y;//数据更新的关键所在：从根节点往下更新，更新的原则是线段只要包含了点x，则要加上更新量y
if(t[z].a==x && t[z].b==x)//更新到子节点了（[x,x]那片叶子），停止
return ;
if(x>(t[z].a+t[z].b)/)//如果该端点x在线段的右边，更新右子树
//如果上个节点是[a,b],则它的左子树为[a,(a+b)/2],右子树为[(a+b)/2+1,b] 这里非常重要(=+-__+=)！！！
Add(x,y,*z+);
else
Add(x,y,*z);//否则更新左子树
}
void Sub(int x,int y,int z)//区间修改Sub 跟Add差不多的思路
{
t[z].s-=y;
if(t[z].a==x&&t[z].b==x)
return ;
if(x>(t[z].a+t[z].b)/)
Sub(x,y,*z+);
else
Sub(x,y,*z);
} void Query(int x,int y,int z)//区间查询Qyery
{
if(t[z].a>=x&&t[z].b<=y)//[x,y]刚好在[a,b]内
ans+=t[z].s;//记录答案
else
{
if(x>(t[z].a+t[z].b)/)//[x,y]在右子树上
Query(x,y,*z+);
else if(y<=(t[z].a+t[z].b)/)//在左子树上
Query(x,y,*z);
else//如果[x,y]在两个子树上都有，都查就行了
{
Query(x,y,*z);
Query(x,y,*z+);
}
}
}
//这里体现的线段树的优越性，在查询的时候不需要全部遍历
int main()
{
int i,j;
scanf("%d",&T);
for(i=;i<=T;i++)
{
scanf("%d",&N);
for(j=;j<=N;j++)
scanf("%d",&n[j]);
Init(,N,);
printf("Case %d:\n",i);
while(scanf("%s",&p),strcmp(p,"End"))
{
if(strcmp(p,"Add")==)//Add 第x个数加y
{
scanf("%d %d",&x,&y);
Add(x,y,);
}
else if((strcmp(p,"Sub")==))//Sub 第x个数减y
{
scanf("%d %d",&x,&y);
Sub(x,y,);
}
else if((strcmp(p,"Query")==))//Query 输出x->y的美观值
{
ans=;
scanf("%d %d",&x,&y);
Query(x,y,);
printf("%d\n",ans);
}
}
}
return ;
}
哦，这里还有一个坑，如果用C++的cin和cout的话，光荣的TLE......小伙伴们不信可以去试试。如果不TLE，希望大神能给我分享一下你的code，感激不尽。