昨天看到殷牛的线段树的程序，里面有个lowbit函数是在看不懂，百度几番后才知道原来是一个与树状数组的函数。

lowbit(x) 函数的返回值是X的2进制最末尾的0的位数（具体原因我也不知道，很神奇，据说是机器运算的成果）

每个下标为i的元素管理的区域为 [i-2^k+1,i] 这个长度为2^k的区域（k为i2进制后末尾的0的个数）

用c[i] 记录i管理区域内的相关元素的个数，这样 通过 i+=lowbit(i);  和 i-=lowbit(i); 就很容易并且很迅速地能够对c数组进行查询和更新（时间复杂度为log(n)）

我还做了一个与树状数组类型的题目 ——POJ 2352

 题目的大意为按从小到大顺序给出坐标系中每个点的坐标，对于每个点来说，按照其左下区域的点的数量（包括线上）给点分等级，统计并输出每个等级的点数。标程如下：（我交后改得更加精炼哈）

＃i nclude <iostream>
＃i nclude <cstring>
＃i nclude <stdio.h>
#define N 32001
using namespace std;
int sum[32010],result[32010];

int lowbit(int x) {return x&(-x); }

int getsum(int x)
{
    int s=0;
    while (x>0) s+=sum[x],x-=lowbit(x);
    return s;
}

void add(int x)   {  while (x<=N) sum[x]++,x+=lowbit(x);   }

int main()
{
    int i,k,y,n;
    memset(sum,0,sizeof(sum));
    memset(result,0,sizeof(result));
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%d%d",&k,&y);
        result[getsum(k+1)]+=1;//查找并更新result数组
      add(k+1);//更新
  }
    for (i=0; i<n; i++) printf("%d\n",result[i]);
    return 0;
}