树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。
在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。
但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。
可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。
当n非常大时，程序会运行得非常缓慢。
因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。
很明显当改变A[i]的值时，需要改变c的值大大减少，而且求和也大大减少。
如图所示，红色矩形表示的数组C[]就是树状数组。
这里，C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，（例如c[6]=A[6-2^1+1]到A[6]的和）
利用位运算，我们可以直接计算出2^k=i&(i^(i-1)或2^k=i&(-i)；
求最小幂2^k:
int Lowbit(int t)
{
return t & ( -t );
}
对某个元素进行加法操作：
void plus(int pos , int num)
{
while(pos <= n)
{
in[pos] += num;
pos += Lowbit(pos);
}
}
求前n项和：
int Sum(int n)
{
int sum = 0;
while(n > 0)
{
sum += in[end];
n -= Lowbit(n);
}
return sum;
}