NYOJ123 士兵杀敌（四）

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=123
题目分析：这里应用的是区间树，不过在插入数据的时候，遇到第一个完全包含与要插入的区间时，将数据加到里面。因为这道题，其实抽象了以后就是，每一次加数据，相当于是在相应的区间上面加，询问的时候，将x通过的每一个区间的数据相加即可。关于区间树的更多介绍，有时间了会来完善的~今天去跳舞咯~

#include<stdio.h>

const int N = 1000002;

struct TREE
{
	int Left;
	int Right;
	int num;
};
TREE tree[N<<2];

void Build(int root, int l, int r)
{
	tree[root].Left = l;
	tree[root].Right = r;
	tree[root].num = 0;
	if(l < r)
	{
		int m = (l + r)>>1;
		Build(root<<1, l, m);
		Build(root<<1|1, m + 1, r);
	}
}

void Insert(int root, int b, int e, int v)
{
	//[b,e]覆盖了root表示的区间
	if(b <= tree[root].Left && tree[root].Right <= e)
	{
		tree[root].num += v;
		return;
	}
	int m = (tree[root].Left + tree[root].Right)>>1;
	//[b,e]位于root的左半区间
	if(e <= m)
		Insert(root<<1, b, e, v);
	else if(b > m)//[b,e]位于root的右半区间
		Insert(root<<1|1, b, e, v);
	else//[b,e]与两个区间都相交
	{
		Insert(root<<1, b, m, v);
		Insert(root<<1|1, m + 1, e, v);
	}
}

int Query(int root, int x)
{
	if(tree[root].Left == tree[root].Right)
		return tree[root].num;
	int m = (tree[root].Left + tree[root].Right)>>1;
	int sum = tree[root].num;
	if(x <= m)//询问x所在的那部分区间
		sum += Query(root<<1, x);
	else
		sum += Query(root<<1|1, x);
	return sum;
}

int main()
{
	int n,m;
	int b,e,v;
	char str[10];
	int i;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		Build(1, 1, m);
		for(i = 0; i < n; ++i)//这里最开始写成m了，被坑了
		{
			scanf("%s", str);
			if(str[0] == 'A')
			{
				scanf("%d %d %d", &b, &e, &v);
				Insert(1, b, e, v);
			}
			else
			{
				scanf("%d", &b);
				printf("%d\n", Query(1, b));
			}
		}
	}
	return 0;
}