$Binary$ $Indexed$ $Tree$ : 树状数组

BIT

首先来看一道例题：（Link）

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

首先按照暴力思路解决，我们用$O(n)$输入，更改的时候是$O(m)$，求区间和的时候是$O(nm)$，然后就会导致程序运行时间非常长，这里我们引用树状数组（$Binary$ $Indexed$ $Tree$），简称$BIT$，是一种非常高效的高级数据结构（$Senior$ $Data$ $Structure$），它的查询和修改的时间复杂度都是$log(n)$。

$1$.基本思想

我们知道，每一个整数都可以分成若干个$2$的幂次之和，就好像$7$可以分解为$2^2$+$2^1$+$2^0$一样，我们希望每一次求前缀和也能够分解为一系列恰当的、不相交的“子集”，$7$分解成了三块，那么我们希望$7$的前缀和也能够分解为$3$个子集。根据这种思想我们可以汇出这样的一个表格：

这里的“内容”指的就是所包含的子集，就比如3只包含3本身，而4包含1~4所有，那么我们为什么要这样划分呢？

在这里我们用$sum[i]$来表示$i$的所有子集的$a[$ $]$的和，然后我们来进行检验，这种求和方案是不是满足我们一开始的初衷，比如，求前缀和$\sum_{i=1}^7a[i]$，我们就只需要计算$sum[7],sum[6],sum[4]$，正好是三个子集，也就是$3$+$2$+$4$=$9$，所以我们知道这种方法看似是成立的。

下面，我们用另一种图来表示“子集和”的含义。

我们按照上面的表格在这里建立了一个方块图，每一个长方形代表的是每个子集对应的部分和，而被框起来的部分就是子集下表对应的值$a[now]$，没有被框起来的部分代表的是还需要维护的其他的下标对应的值$a[k...now-1]$。我们首先来看$1$节点，它的维护路径是这样的：

然后对于$3$的维护是这样的路径：

由此，我们还可以构造出一种更一般的形式：查询树。

对于每一个查询，我们在查询树中找到对应标号的节点，然后顺着父边一直向根节点方向走一直到$0$，依次累加路径上每一个标号所对应的子集和，到根节点的时候,我们就得到了$ans$。比如$7$，我们沿路就要加上$7$,$6$,$4$的$sum$值。而节点的深度就是对应数字的二进制表示当中$1$的个数。比如$11$的二进制拆分是$1011$，含有$3$个“$1$”，那么对应的深度就是$3$。另外还有一个十分重要的规律，（除了$0$节点之外）

每一个节点的儿子个数都是这个点的二进制表示中末尾$0$的个数。

比如$4$的二进制拆分$0100$，末尾有$2$个$0$，那么它的儿子个数就有$5$,$6$一共两个。而树状数组的名字$Binary$ $Indexed$ $Tree$也就是这么来的。

$2$.实现

现在我们就是要考虑怎么实现这种子集划分。我们再来看一个表格。

那么我们可以知道，$i$所含元素的个数就是$i$的二进制拆分的最低位的1所在的位置的十进制数。 那么这个位置又该怎么算呢？

下面要讲的是树状数组中最重要的一个技术：低位技术，即$Lowbit$，对于一个下标$now$,我们知道$now$是用的有符号的整形数进行存储的，其次，我们还知道计算机存储整形数是用补码的形式，正数的补码就是本身的二进制码，而其相反数则是用的其反码+$1$来表示。假设$now$的二进制数为$x1y$,其中$y$为若干个$0$，那么$x$和$y$中间的$1$就是最低位的$1$，那么-$now$就是$($~$x)1y$ (~$x$表示对$x$取非，~$1011=0100$)，那么两者$and$之后就得到了$1y$，那么我们不难得知$now$的$Lowbit$是怎么算出来的。

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

然后我们还要知道一个定律：在我们所建的树状数组中，儿子$i$加上$lowbit(i)$就是其父亲的编号，这个也不难想。那么对于前缀和的查询我们就有头绪了，对于下标为$now$的前缀和，我们需要加的项的个数是$now$的二进制拆分中所包含的1的个数，也就是在查询树的深度，这个个数最多是$trunc(log_2now)+1$,所以查询复杂度是$O(logn)$的。

int query(int now){//询问now的前缀和
    int ans=0;
    while(now){
        ans+=sum[now];
        now-=l
    }
    return ans;
}

然后对于单点修改就很简单了，我们可以类比线段树，由于我们的节点存储的是一种和的形式，所以当任意一个子节点发生改变的时候，父节点也要发生改变，所以我们的单点修改也是一个while()形式。

void add(int now,int k){//将下标为now的数加上k
    while(now<=n){
        sum[now]+=k;
        now+=lowbit(now);
    }
}

至此，是树状数组的基本部分，下面是开头的题的代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010
using namespace std;
int sum[MAXN],n,m;
int lowbit(int now){
    return now & (-now);
}
void add(int now,int k){
    while(now<=n){
        sum[now]+=k;
        now+=lowbit(now);
    }
}
int query(int now){
    int ans=0;
    while(now!=0){
        ans+=sum[now];
        now-=lowbit(now);
    }   return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        add(i,x);
        //我们可以把输入也理解为一种单点修改
    }
    for(int i=1;i<=m;i++){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1) add(x,y);
        else printf("%d\n",query(y)-query(x-1));
    }   return 0; 
}

然后是第二道例题，涵盖了树状数组的另外两种功能：区间修改和单点询问。

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的和、

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x 含义：输出第x个数的值

输出格式：

输出包含若干行整数，即为所有操作2的结果。

在这里我们介绍一种利用查分数组解决问题的方法，首先我们要知道什么叫做差分数组，简而言之，就是原序列中相邻元素之间两两相减，得到的一串数组。举个例子，假设$a[9]$={$2,5,9,5,4,8,6,6,1$},那么$a$的差分数组$b[9]$={$2,-3,4,-4,-1,4,-2,0,-5$}。也就是说$b[i]$=$a[i]$-$a[i-1]$,从而可以得到$a[i]$=$\sum_{j=1}^i b[j]$。

接下来，假设我们需要将$3$~$7$之间的所有数加上$5$，那么原序列变为：$a[9]$={$2,5,14,10,9,13,11,6,1$}，b[9]={$2,-3,7,-4,-1,4,-7,0,-5$}。

$OK$，那么我们现在就可以发现规律了，$a[]$数组对$x$~$y$加上$k$之后，$b[]$数组只是在$x$位置加上$k$，在$y$+$1$位置减去$k$，即$b[x]+-k; b[y+1]-=k$; 那么在修改的时候我们就由一串区间修改变为了两个单点修改。而单点查询就变为了区间查询，那么这个区间查询我们就可以在此利用树状数组维护了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010
using namespace std;
int a[MAXN],sum[MAXN],n,m;
int lowbit(int now){
    return now&(-now);
}
void add(int now,int k){
    while(now<=n){
        sum[now]+=k;
        now+=lowbit(now);
    }
}
int query(int now){
    int ans=0;
    while(now!=0){
        ans+=sum[now];
        now-=lowbit(now);
    }   return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int b=a[i]-a[i-1];//差分 
        add(i,b);
    }
    for(int i=1;i<=m;i++){
        int opt; cin>>opt;
        if(opt==1){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            add(x,k); add(y+1,-k);//两个单点修改 
        }   else{
            int x; scanf("%d",&x);
            printf("%d\n",query(x));//前缀和查询 
        }
    }   return 0;
}