定义

树状数组是一个查询和修改复杂度都为log⁡n\log{n}的数据结构。主要用于数组的单点修改和区间求和。广义上来说，能够动态维护前缀和。基本上树状数组能做的事情，线段树都能做，反之就不一定了。所以线段树更加强大。但是线段树代码太难写了。

和线段树的区别

  1. 两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树。
  2. 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决。
  3. 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。

上面出现了一个新名词: lowbit.其实lowbit(x)就是求x最低位的1。

具体做法


其实树状数组是用一个连续的数组来存储树的结构，t[x]保存以x为根的子树中叶节点值的和。上图中的a[n]是原数组。

而且每一个节点覆盖的长度就是lowbit(x)。
t[x]节点的父节点为t[x+lowbit(x)]。
而且整棵树的深度为log⁡n+1\log{n}+1。

lowbit

1
2
3
4
int lowbit(int x){
    return x&(-x);
}

单点修改

以add(x,k)操作为例。

1
2
3
4
5
void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        t[i]+=k;
    }
}

区间求和

以ask(x)操作为例。

1
2
3
4
5
6
7
int ask(int x){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        res+=t[i]
    }
    return res;
}

要求区间[x,y][x,y]的和时，可以使用前缀和ask(y)-ask(x-1)来求出它。

下面的这些扩展函数add ask函数内部操作还是一样的。就是外部有差别。

区间修改、单点查询

引入差分数组b[n]，作为原数组a[n]的增量数组（不用对这个树状数组预处理）。用树状数组来维护这个数组。
而后区间修改的操作和差分数组一样，使用add(l,d)和add(r+1,-d)来完成。
查询原数组a[x]的值时，因为差分数组的前缀和等于原数组，所以可以用a[x]+ask(x)来完成。（有了a[x]不用对树状数组预处理了）
这个地方的操作和差分数组是一样的。只是单点查询时，复杂度会低一些。

区间修改、区间查询

sumx=∑i=1xax=∑i=1x∑j=1idi=∑i=1x(x−i+1)×disum_x=\sum_{i=1}^{x}a_x=\sum_{i=1}^{x}\sum_{j=1}^{i}d_i=\sum_{i=1}^{x}(x-i+1)\times d_i
由之前的差分数组帖子可知上式。如果要进行区间修改，维护差分数组b[x]就可以了，但是这样只能更新到单点a[x]，再想区间查询，最好对a[x]再做一个前缀和。显然这里会用到两个树状数组。但是去求区间查询很麻烦，可以用下面这个式子转换着去求。

设树状数组t1t_1维护b[i]前缀和，t2t_2维护i*b[i]前缀和。
这里的b[i]依旧是增量数组。

那么区间修改[l,r][l,r]加上dd：

1
2
3
4
5
6
7
add1(l,d)
add1(r+1,-d)
//维护数组b[i]

add2(l,l*d)
add2(r+1,-(r+1)*d)
//维护数组i*b[i]

区间查询[l,r][l,r]的和：

1
2
3
4
ans=sum[r]-sum[l-1]+((r+1)*ask1(r)-ask2(r))-(l*ask1(l-1)-ask2(l-1))

// (x+1)sum(b,x) = (x+1)ask1(x)
// sum(i*b,x) = ask2(x)

其他

对于一个数组，可以用树状数组前缀区间维护和、异或和、最大值、最小值等等。

参考资料

[1] https://blog.csdn.net/bestsort/article/details/80796531
[2] https://blog.csdn.net/qq_41021816/article/details/81167388
[3] https://www.bilibili.com/video/BV1pE41197Qj