树状数组

引子

对于一段区间，前缀和数组和普通数组对 单点修改和区间查询 两种操作支持的复杂度

单点修改: 前缀和数组 $O(N)$，普通数组$O(1)$

区间查询: 前缀和数组$O(1)$，普通数组$O(N)$

当单点修改和区间查询的操作都比较频繁时,运行时间取决于最坏的操作，N次操作复杂度达$O(N^2)$​

前置知识

对于任一段区间$[L,R]$​，我们可以转化成对$[1,R]$​和$[1,L-1]$​的操作。因此考虑模型时，先搞清楚$[1,X]$​.

对于区间$[1,X]$​，长度为$X$。对于数$X$,借用二进制拆分的思想，可以把$X$拆成二进制上单独的$1$的加和。

如:$7=4+2+1=2^2+2^1+2^0$

套用到区间上，我们同样可以把区间$[1,7]$​按照区间长度拆成$[1,1]+[2,4]+[5,7]$​或者说$(0,2]+(2,4]+(4,7]$​​​

如果求$[1,7]$的区间和，可直接由各个子区间的和推出来，我们只需要知道子区间的区间和即可

考虑到各个方面，树状数组拆区间虽然也是和二进制位有关，但是为了计算(后面提到)，并不是按照这个顺序拆的。

$[1,7]=(7-1,7]+(7-1-2,7-1]+(7-1-2-4,7-1-2]$

​ $=(7-1-2-4,7-1-2]+(7-1-2,7-1]+(7-1,7]$

​ $=(0,4]+(4,6]+(6,7]$ ⭐​

观察性质

对于拆好的区间，可以发现区间长度$len$​和区间右端点$R$​​之间有关系，在这之前先定义一个操作$lowbit$

$lowbit(x)$:返回$x$二进制下最末位的那个$1$

如:$lowbit(6)=2,lowbit(4)=4,lowbit(7)=1$​

$lowbit$的实现

1. 为求出$lowbit(x)$​​，最朴素的做法: 从最后一位向前寻找​ ,令该位和$1$​按位相与，得1则立即返回 1<<(第几位)

2. 如果对计算机对变量的二进制表示比较熟悉，了解补码的形式，则就能看懂这个表述形式

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

   如$lowbit(7)=7$​​&$-7$​​

   ​ $=(0111{)}_2$​​​&$(1001{)}_2$​​​​

   ​ $=1$

   注意:

   这里所说的返回的 ‘$1$​​​“,不是单纯返回个1，而是说返回$x$二进制表示下的末位$1$​的位数 对应的十进制数

   $lowbit(x)$也可以等价成$2^k$($k$指的是末尾连续0的数目)：$lowbit(6)=2^1$​

​ 关于$lowbit$​操作的叙述到此为止，我们接着对区间的性质分析

$[1,7]=(0,4]+(4,6]+(6,7]$​

区间$(0,4]$的长度为$lowbit(4)=4$

区间$(4,6]$的长度为$lowbit(6)=2$

区间$(6,7]$​的长度为$lowbit(7)=1$​

看上去我们发现了一个令人震惊的真相，实际上这在我们拆区间的时候已经决定好了

我们拆区间$[1,x]$时，是按照$x$​的二进制位从低位到高位依次拆的，计算的时候也即是

$lowbit(x)$，$lowbit(x-lowbit(x))$ ,$lowbit(x-lowbit(x)-lowbit(x-lowbit(x)))$​……

上式也改写成

$[1,7]=(4-lowbit(4),4]+(6-lowbit(6),6]+(7-lowbit(7),7]$

通过$lowbit$我们可以快速将一段区间$[1,X]$拆成子区间

回归正题

上面讨论了将区间按照二进制拆分所相关的性质。

接着说，如何利用这些东西进行区间查询和单点修改

区间查询: 通过二进制枚举子区间，得出大区间

我们把原数组记为$A$，$A$的每一个下标$i$对应的$A[i]$则对应着单点的值，(这是废话，无需多言

引入一个辅助数组$C$​，就像引入前缀和数组一样。$C[i]$​定义为储存$A$​数组的一段区间和$C[i]=[i-lowbit(i)+1,i]$​​

或者写做$C[i]=(i-lowbit(i),i]$​

$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$​数组下标存储的值还有着联系，如下图

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

$C[8]=A[8]+C[7]+C[6]+C[4]$​

以$8$为例，$lowbit(8)=8$​，包含的区间长度为$8$

减去自己对应的$A[8]$​这一区间，得$(0111{)}_2$​

按照二进制划分区间

$(0110,0111],(0100,0110],(0000,0100]$​

即可有$C[8]=A[8]+C[7]+C[6]+C[4]$​​，注意$C[i]$​​​的定义和所指的区间的长度

上面的讨论是说，求数组$C$​时，不必蛮力运算。直接根据下标的关系可以推知

区间查询

求$(0,x]$​​​​的前缀和

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

任何区间都可以这样，通过划分好的子区间求得

于是进行区间查询时，我们先将其转化位两个前缀和样式的区间。再通过区间划分，由子区间推出大区间，即可求得。

单点修改

例如，我们要修改$A[4]$​，发现在上图中直接包含$A[4]$​的$C$​数组为$C[4]$​,于是修改$C[4]$​即可

$C[8]$直接包含$C[4]$，再通过$C[4]$修改$C[8]$，依次向上进行修改，这种包含关系就像一颗树一样，每个数只被一个数直接包含

也即可得出时间复杂度为$O(logN)$​

具体如何快速找到，划分区间时是以$lowbit(i)$​为长度划分的，定位父区间时，加上$lowbit(i)$​向回推进即可

代码

void add(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i))
        C[i]+=val;
}

建立树状数组的时候，也只要对每个单点进行修改就行$O(NlogN)$​

void init(){
    for(int i=1;i<=n;i++){
        add(i,A[i]);
    }
}

扩展应用

单点修改，区间查询

这是树状数组的基操

区间修改，单点查询

单点可以看做长度为$1$的区间，但是区间修改怎么办呢?

看到区间修改，会想到差分的做法。其实树状数组＋差分就可以完成区间修改这一做法，但是意味着 不再支持区间查询

我们再创建一个差分数组$diff[i]=A[i]-A[i-1]$，树状数组$C$维护$diff$的信息

现在树状数组还是进行单点修改和区间查询的操作，但是操作对象换成了$diff$

1. 进行单点修改，回想一下差分是如何做到给区间加和的，给区间$[L,R]$加上值$s$，只需:$diff[L]$+=$s$,$diff[R+1]$-=$s$​​。我们发现 完全可以用树状数组达到
2. 进行区间查询，对差分求前缀和，即得到原数组，这也是完全$ok$​的

代码不表(滑稽

区间修改，区间查询

看起来比前面复杂许多，实际上就是复杂许多

考虑到区间修改操作，我们仍然计划让树状数组维护差分，现在开始分析性质

为了方便，记原数组为$a$，差分数组为$b$，树状数组为$c$

那么很明显:$a[i]={\sum }_{j=1}^{j=i}b[j]$，现要计算前缀和$[1,x]={\sum }_{i=1}^{i=x}a[i]={\sum }_{i=1}^{i=x}{\sum }_{j=1}^{j=i}b[i]$​

如果画图，可以发现$b[i]$​​​​​的值实际上是三角形

我们要算的也就是红色部分圈出来的值，假设我们要运算的是$[1,x]$​区间里的值

$[1,x]=x\ast b_1+(x-1)\ast b_2+(x-2)\ast b_3+\dots \dots +b_x$​

发现，规律难寻，或者说，很难转化成树状数组求解

现在将其补全为一个矩阵的形式

那么可以得到:$[1,x]=(x+1)\ast {\sum }_{i=1}^x{b}_i-{\sum }_{i=1}^x(i\ast b_i)$​

我们可以通过维护两个树状数组，一个维护$b$另一个维护$i\ast b$，通过二者的组合得出前缀和

此外，树状数组还有一些其他的应用，举几个例子

1.二维树状数组
2.如何$O(N)$时间复杂度建树状数组

但是,我们有大杀器线段树,何必难为自己呢