学步园

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=116
题目分析：
做这道题，还是学到了一些东西。
1）负数在内存中的存放形式。为什么要说这个呢，因为在下一步，数组中每个元素的父节点时，需要求得i的二进制中最右的一个1。在计算机中负数是以补码的形式存放的。负数的补码怎么求呢？比如说数-5，八位为例，二进制位10000101，其反码是除了符号位以外，按位取反，则为111111010，其补码是反码加1，即11111011。那5的原码是00000101。则-5&5正好就是00000001。这就求得最右边的一位1了。
2）树形数组。将数组看成一个数，然后进行累计求和或者进行增加删除时，只需要遍历O(log(n))就可以了。其实数组中第i个数的父节点是i+(i的二进制最右边的1所在位的2的方幂)。不知道说清楚了没有。比如说奇数，最右边的1是在第0位，即2^0=1；如果是4，最右边的2在第2位，故为2^2=4；

#include<stdio.h>
#include<string.h>
int arr[1000005];
char str[7];

inline int xb(int x)
{
	return x&(-x);
}

int Sum(int x)
{
	int sum = 0;
	while(x > 0)
	{
		sum += arr[x];
		x -= xb(x);
	}
	return sum;
}

void Add(int a, int b, int n)
{
	for(int i = a; i <= n; i += xb(i))
		arr[i] += b;
}

int main()
{
	int i;
	int n,m;
	int b,e;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(i = 1; i <= n; ++i)
			scanf("%d", &arr[i]);

		for(i = 1; i <= n; ++i)
		{
			if(i + xb(i) > n)
				continue;
			arr[i + xb(i)] += arr[i];
		}

		for(i = 0; i < m; ++i)
		{
			scanf("%s", str);
			scanf("%d %d", &b, &e);
			if(!strcmp(str, "QUERY"))
				printf("%d\n", Sum(e) - Sum(b - 1));
			else if(!strcmp(str, "ADD"))
				Add(b, e, n);			
		}	
	}		
	return 0;
}