题目： http://acm.hdu.edu.cn/showproblem.php?pid=1166
简单题，1A了，这个好像就是传说中的“点树”。
设当前结点表示线段[left, right]，编号为i，则结点的左孩子表示线段[left, mid], 编号为2*i，右孩子表示线段[mid+1, right], 编号为2*i+1。
#include <stdio.h>
#include <string.h> const int MAXN = ; //线段树的结点，分别表示一条线段的左端点、右端点、增加的人数
struct Tree_Node
{
int left;
int right;
int num;
}tree[*MAXN]; //建立线段树，left和right对应线段树结点中的left和right，i表示当前结点的线段树编号
void build(int left, int right, int i)
{
tree[i].left = left;
tree[i].right = right;
tree[i].num = ;
if(left == right)
{
return;
}
int mid = (left + right) / ;
build(left, mid, *i);
build(mid+, right, *i+);
} //插入到线段树，tar表示增加人数的那个点在数轴上的编号（不是在线段树上的编号）
//num表示增加的人数，step表示当前结点的线段树编号
void insert(int tar, int num, int step)
{
if(tree[step].left <= tar && tree[step].right >= tar)
{
tree[step].num += num;
}
if(tree[step].left == tree[step].right)
{
return;
}
int mid = (tree[step].left + tree[step].right) / ;
if(tar <= mid)
{
insert(tar, num, step*);
}
else
{
insert(tar, num, step*+);
}
} //left和right表示查询的区间，step表示当前结点的线段树编号
int query(int left, int right, int step)
{
if(tree[step].left == left && tree[step].right == right)
{
return tree[step].num;
}
int mid = (tree[step].left + tree[step].right) / ;
if(right <= mid)
{
return query(left, right, step*);
}
else if(left > mid)
{
return query(left, right, step*+);
}
else
{
return query(left, mid, step*) + query(mid+, right, step*+);
}
} int main()
{
int t, n, x;
scanf("%d", &t);
for(int item = ; item <= t; item++)
{
scanf("%d", &n);
build(, n, );
for(int i = ; i <= n; i++)
{
scanf("%d", &x);
insert(i, x, );
}
char cmd[];
int a, b;
printf("Case %d:\n", item);
while(scanf("%s", cmd) != EOF && cmd[] != 'E')
{
scanf("%d %d", &a, &b);
if(cmd[] == 'Q')
{
printf("%d\n", query(a, b, ));
}
else if(cmd[] == 'A')
{
insert(a, b, );
}
else if(cmd[] == 'S')
{
insert(a, -b, );
}
}
}
return ;
}