树状数组

• 树状数组的原理是增加一个辅助序列C数组，令c[i]=a[i-2k+1]+a[i-2k+2]+…+a[i]，其中k为i在二进制形式下末尾0的个数。

总共三个函数

1. lowbit(i)函数

• 该函数的意思是: 返回参数转为二进制后，最后一个1的位置所代表的数值。
  该数比如6 (110) -> (010), 结果为2。
• lowbit(i) = 2^k
• 参考代码：

int lowbit(int x) //求子叶数
{
    return (x)&(-x);
}

2. update(int k,int num)函数

• 更新操作，比如要更新a[i]，则需要更改从该叶子节点a[i]到根节点路径上的所有c[j]。
• 参考代码：

void update(int k, int num)  //更新数据
{
    while (k <= n)
    {
        c[k] += num; 
        k += lowbit(k); //找父节点
    }
}

3. sum(int k)函数

int sum(int k) //求1~k的区间和
{
    int sum=0;
    while(k)
    {
        sum+=c[k];
        k-=lowbit(k); //求父节点的下一个左子节点
    }
    return sum;
}

4. 求区间a[i]+…+a[j]的和

• 可以先统计出a[1]+a[2]+…+a[i-1]的和，在统计a[1]+a[2]+…+a[j]的和，两者相减即可得到a[i]+…+a[j]的和。即=sum(j)-sum(i-1)；