树状数组的理解以及简单应用

树状数组的应用其实就是一个巧妙地运用了二进制运算来进行 logn 插入、 logn 查询 的 前缀和 算法。

原理分析：

假设有 9 个数字组成的数组：

 A[] = 1  2  5  4  3  7  8  6  9

我们使得树状数组 c[] 以以下方法存储：

C[1] = A[1]

C[2] = A[1] + A[2]

C[3] = A[3]

C[4] = A[1] + A[2] + A[3] + A[4]

C[5] = A[5]

C[6] = A[5] + A[6]

C[7] = A[7]

C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

C[9] = A[9]

这样我们是看不出来咋存滴，我们先写成 二进制 再来看看：

C[1] = A[1]

C[10] = A[1] + A[2]

C[11] = A[3]

C[100] = A[1] + A[2] + A[3] + A[4]

C[101] = A[5]

C[110] = A[5] + A[6]

C[111] = A[7]

C[1000] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

C[1001] = A[9]

重点来了，现在我们来构造 C 数组 ，我们观察 A[] 在哪里出现过：

A[1] →→  C[1] 、C[10] 、 C[100] 、C[1000]

A[2] →→  C[10] 、C[100] 、C[1000]

A[3] →→  C[11] 、C[100] 、C[1000]

A[4] →→  C[100] 、C[1000]

A[5] →→  C[110] 、C[1000]

A[6] →→  C[110] 、C[1000]

......           ..........................

好我现在告诉你啥规律~

比如我们来看 A[3] ： 3 的二进制是 1 1 ，它先对自己的 C[3（11）] 有贡献，故 C[3] += A[3] 。然后 A[3] 再对 C[4（110）] 有贡献，故 C[4] += A[3] 。同样，它还对 C[8（1000）] 有贡献，即 C[8] += A[3] 。

那 3 是如何一步一步转化成 4 、8 的呢？

3 的二进制是 1 1    1 1 保留它最低位的 1 ，其它位的 1 去掉（即变为 0），则有：0 1 ，然后使 1 1 加上 0 1 → 1 0 0 （即 4）

4 的二进制是 1 0 0    1 0 0 保留它最低位的 1，则有：1 0 0 ，然后使 1 0 0 加上 1 0 0 → 1 0 0 0（即 8）

其他什么，A[1] 、A[2] ......同理，大家可以试着写一下

那么 “ 保留它最低位的 1 ，其它位的 1 去掉（即变为 0）” 这句话所变成的二进制，再转化为十进制数的值，如何求呢？

 这里需要一个 自定义的 lowbit 函数，这个函数可以得出上面问题的答案：

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

故我们可以构造出树状数组了~（实现看注释）

inline void update(int x,ll k)  // x 表示 c[i] 中的 i ，k 表示 为当前 c[x] 贡献的值
{
    while(x<=n){ //当然超出 c 数组长度的，就不需要构造。比如 x=3 x=4 x=8 然后再到 x=16 ，16我们就不要存了，因为题目我只需要 C[1] 到 C[9] 的值
        c[x]+=k;
        x+=lowbit(x); // 比如上面的例子A[3]，这样写就可以使得 x=3 转化为 x=4 x=8 ，然后 c[4]+= A[3] ,c[8]+= A[3] 了
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        update(i,a[i]);
    }
}

那么构造出了 C数组，如何求出前缀和的呢？

比如现在要知道

A[1] + A[2] + A[3] + A[4] + A[5] 的值：  C[5] + C[4]  ， 5 的二进制： 1 0 1 ， 4 的二进制： 1 0 0 ，差 0 0 1 

A[1] + A[2] + A[3] + A[4] + A[5] + A[6] 的值： C[6] + C[4] ， 6 的二进制： 1 1 0 ，4 的二进制： 1 0 0 ，差 0 1 0 

那 A[1] + A[2] + ..... + A[9] 的值： C[8] + C[9] ， 9 的二进制： 1 0 0 1 ， 8的二进制： 1 0 0 0 ，差 0 0 0 1

而现在我们可以观察到：

5 与 4 的差值为 5 - lowbit（5）

6 与 4 的差值为 6 - lowbit（6）

9 与 8 的差值为 9 - lowbit（9）

跟构造 C 数组一样，每次用 ans += C[x] ，然后 x-=lowbit（x） ，直到 x 自己减自己，为 0 时结束，这样我就能得到 1 ~ x 的前缀和了~

ll query(int x)
{
    ll ans=0;
    while(x){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

到这里，树状数组的板子就完成了~ 总代码在这：

#include<iostream>
#include<algorithm>
#include<string.h>
#define maxn 500008
using namespace std;
typedef long long ll;
int n;
ll a[maxn],c[maxn];
ll lowbit(ll x){return x&(-x);}
inline void update(int x,ll k)
{
    while(x<=n){
        c[x]+=k;// 依次把 k 加入到能贡献的 C 中
        x+=lowbit(x); // x 往上移
    }
}
ll query(int x)
{
    ll ans=0;
    while(x){
        ans+=c[x]; // 通过累加获得前缀和
        x-=lowbit(x);    // x 往下移
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        update(i,a[i]);    //将 a[i] 所能提供的贡献，加入到 C 数组中
    }
    for(int i=1;i<=n;i++){ // 依次求前缀和
        printf("%lld ",query(i) );
    }
    cout<<endl;
}