树状数组详详详解（求逆序对）

参考资料

http://blog.csdn.net/lulipeng_cpp/article/details/7816527

树状数组应用

1. 单点更新

2. 区间求值

3. 求逆序对

lowBit()函数

我们先来了解一下这个函数，简单的一行，求出了x的二进制形式从右往左数第一个1的权值（从0算起）。比如，x=6=110，那么第一个1的位置在1，那么函数就返回2^1=2。

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

单点更新

任一节点更新，其父节点也都要更新。比如要将C[4]+1，那么4+(4&(-4))=8，C[8]要+1，8+(8&(-8))=16，C[16]也要+1……凡是小于n(n为数组的长度)且与C[4]有关的节点都要更新。

void modify(int pos,int num){    //pos为数组下标位置，num为要增加的值
    while(pos<=n)   //n为数组的长度
    {
        C[pos]+=num;
        pos+=lowBit(pos);
    }
}

求前缀和

比如要求A[1]+A[2]+……+A[12]，那么C[12]=A[9]+…+A[12]，C[8]=A[1]+…+A[8]，sum=C[12]+C[8]

int add(int pos)     //求A[1]+…+A[pos]
{
  int sum=0;
  while(pos>0)
    {
        sum+=C[pos];
        pos-=lowBit(pos);
    }
    return sum;
}

树状数组的优点

原本求长度为n的数列的和的时间复杂度为O(n)，现在为O(logn)。

应用：求逆序对