树状数组

一、引入

树状数组（Binary Indexed Tree，BIT）是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。它可以解决大部分区间上面的修改以及查询的问题。

比如：给出一个长度为n的数组，要求实现两个函数，一个是add(int x,int k)将第x个数加上k，另一个是sum(int x,int y)求区间[x,y]中元素的和。因为要频繁地修改值，所以最基础的前缀和是不满足要求的，可以使用树状数组来解决这个问题。

二、实现

假设序列如下所示：

我们需要对某个区间求和，我们可以遍历求和，也可以提前处理一下：

处理之后，我们求和就会快很多。加入我们要计算前15个元素，只需要计算4个数的和即可：

仔细观察，我们会发现，其中有很多是数据不是必须的，因为我们可以通过其他数来间接求得：

我们完全可以将其删去，然后将剩下的数据存放到一个数组t[]中：

当我们需要修改某个节点值时，也只需要修改包含这个节点的部分即可：

把它抽象成一个树形结构（只取了一半），根节点的值是左右子树的和，即t[4] = t[2] + t[3] + a[4]

再看一个函数：lowbit(int x)：

这个函数是计算二进制表示中，最低位为1及其后面的0构成的数在10进制中是多少。

比如44 = （101100）2 最低位为1及其后面的0构成的数是（100）2 = 4；那么该怎么求呢？

44 = (101100)2，我们对44的二进制数取反+1，也即~44+1,得到-44

-44 = (010100)2，然后我们把 44 和 -44 的二进制进行按位与运算，得到二进制(000100)，也就是十进制的4。

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

其实存在一个规律，树状数组中节点x的父节点为x + lowbit(x),例如t[2]的父节点为t[4] = t[2 + lowbit(2)]

根据这个规律，我们就可以很方便的修改某个节点的值了：

int add(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i)) // 小于n防止越界
        t[i] += k;
}

还存在一个规律，6 = 7 - lowbit(7); 4 = 6 - lowbit(6);

根据这个规律区间查询也就容易实现了。比如要求前7项的和，可以通过t[4] + t[6] + t[7]求得

int sum(x)
{
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        sum += t[i];
    return sum;
}

利用前缀和的性质，便可求得任意区间的和。[L,R] = [1,R] - [1,L-1];

int search(int L, int R)
{
    int ans = 0;
    for (int i = L - 1; i > 0; i -= lowbit(i))
        ans -= t[i];
    for (int i = R; i > 0; i -= lowbit(i))
        ans += t[i];
    return 0;
}