---恢复内容开始---
http://poj.org/problem?id=2352
这是一个树状数组的题目，也是我第一次接触这类的题目，也正是因为之前的一道题，TLE了，超时太严重了，我看discuss里再说什么用树状数组可以我才去找有关于这方面的博客看
看了很多博客才稍微的理解了一点树状数组，可以在以后的做题中，加强对这个的理解
这个图片就是数组数组的内涵所在
其中A数组就是原数组，而C[n]=a[n-2^k+1]+.......+a[n]的值，其中K为二进制下的末尾0的个数，比如c[8],8(1000)有3个0，所以，k=3，则C[8]就表示从a[1]到a[8]的值；
int lowbit(int x)
{
return x&(-x); //这个就是用来返回2^k的值的。
}
而对于查询来说的话
求(1,8)的值就是为C[8]
而求(4,8)的值时则可以用C[8]-c[3]-c[2];
也就是sum（a,b）=sum(1,b)-sum(1,a-1);
int sum(int end) //计算原数组1-end的和
{
int sum=;
while(end>)
{
sum+=c[end];
end-=lowbit(end);
}
return sum;
}
关于上面的第6-7行，我觉得举两个实例更加容易理解
比如说要求1-8的和也就是c[8];
首先end=8;
也就是sum=c[8];
而lowbit=8,所以，sum=c[8];
而当end=7；时
首先sum=c[7];
而7（111）所以C[7]=a[7];
lowbit(7)=1;
所以接下来就是sum=c[7]+c[6];
6(110)所以，c[6]=a[5]+a[6]；
end=4;
在接下来就是sum=c[7]+c[6]+c[4];
4(100)所以，c[4]=a[1]+....+a[4];
end=0;
不得不说，这个确实很巧妙
对于更新的话，这个只有一个点一个点的进行更新
下面为从a[pos]的位置上加一个num:
void update(int pow,int num)
{
while (pow<=n)
{
c[pow]+=num;
pow+=lowbit(pow);
}
}
其实有了上面的的举例之后，也可以感觉得到在某个位置上加个数之后，只不过是在被C包围的那个位置上加上个数，所对应的C也自然而然的加，
且这个有局限性就是只可以对于单个节点进行更新
对于二维数组数组
下面的代码给a[i][j]这一节点加上个K
void update(int i,int j,int k)
{
while (i<=n)
{
int temp=j;
while(temp<=n)
{
c[i][temp]+=k;
temp+=lowbit(temp);
}
i+=lowbit(i);
}
}
下面就是关于POJ2352的一个解题代码
#include <stdio.h>
#include <iostream> using namespace std; int n;
int level[]; //level就是用来存等级的
int c[]; //树状数组
int lowbit(int x)
{
return x&(-x);
} int sum(int x) //求和
{
int s=;
while(x>)
{
s+=c[x];
x-=lowbit(x);
}
return s;
} void update(int pos) //更新，因为树状数组么，所以它肯定是更新到最顶端！
{
while(pos<=)
{
c[pos]++;
pos+=lowbit(pos);
}
}
int main()
{
scanf("%d",&n);
int x,y;
for(int i=;i<=n;i++)
{
scanf("%d%d",&x,&y);
level[sum(x+)]++; //每次多一个之后，sum(x+1)所对应的那个等级就会++，而为什么是X+1的目的就是避免X=0，而且不会影响其的相对位置，如果不理解，多看几遍就会懂其内涵
update(x+);
}
for(int i=;i<n;i++)
{
printf("%d\n",level[i]);
}
return ;
}