树状数组从入门到不会（超详细）

2023-10-04 13:47:16

树状数组

这是一种基于二进制思想的数据结构，他的主要功能是维护前缀和，支持修改与求和两种操作（复杂度都是O(nlogn))，这其中又分为单点修改，区间修改，区间查询，本文会依次介绍。

入门

对于一个数，我们可以用他的二进制表示来把他拆成几个小区间，以（10101）为例，它可以拆成 $2^4 + 2^2 + 2^0$ 所以就可以得到三个区间分别为 $ \left [ 1,2^4 \right ] \left [ 2^4+1,2^4+2^2 \right ] \left [ 2^4+2^2+1,2^4+2^2+2^0 \right ]$

进而我们可以知道，对于查询一个结尾为 $i$ 的区间，得到的区间长度就是二进制下他最小的2的幂，定义为 $lowbit(i)$ 要想求出他也很简单，就是 $i$ & $-i$ ，因为计算机中负数使用的是补码表示法，也就是按位取反再加一，这会使原来的0变成1，1变成0，然后加一又会使原来低位的0重新变回0，直到原来最低位的1重新变回1，故而得到了$lowbit$ 不理解可以手推一遍。

到此，我们可以建立一个树状数组，$c[i]$ 存储了给定序列$A$中 $\left [ i-lowbit(i)+1,i \right ] $区间的元素和，也就是以$i$ 为根节点的子树的叶子结点的和，也不难发现，该节点的父亲节点为 $c[i+lowbit(i)]$ ，他有 $lowbit(i)$个叶子节点。

附上我们构造出的数组结构图片，就能理解为什么叫树状数组了

百度yyds

单点修改

这颗数的深度是$log$的，因此对每个元素的修改操作，在树状数组中只需要 $log$的修改，是不是很棒呢。

我们只需要不断寻找当前节点的父亲节点，也就是加上$lowbit(i)$ 并给他们也加上这个元素，就可以啦

inline void update(int i,int x){
    for(;i<=n;i+=lowbit(i))c[i]+=x;
}

$c$是我们的树状数组，$i$是原序列修改的点，$x$是加上的数。

查询区间前缀和

我们可以发现，对于当前的$c[i]$ 他求出了 $\left [ i-lowbit(i)+1,i \right ] $区间的元素和，那么我们只需要每次减掉$lowbit(i)$就可以得到下一个大区间的和，累加即可得到前缀和，复杂度显然也是$O(logn)$的

inline int sum(int i){
    int ans = 0;
    for(;i;i-=lowbit(i))ans+=c[i];
    return ans;
}

完结撒花~~~

恭喜你，看到这里已经成功入门了树状数组。

接下来我们介绍对于他的升级：

区间修改：对给定区间同时加减一个数k & 单点查询：查询修改后给定位置元素的值

乍一看是不是感觉会非常非常非常非常非常非常麻烦。

不过我们有个好东西，叫差分数组，如果还不了解的话请自行百度。

众所周知，差分与前缀和是互逆操作，说成人话就是：差分的前缀和就是原数列$A$，前缀和的差分也是原数列$A$。

看到这里是不是有点眉目了？

是的，在这里我们的差分数组不再是原数列$A$的前缀和，我们可以先引入一个数组$d$,$A{}'[i] = d[i] + A[i]$ 也就是说，$d[i]$记录了$A[i]$被修改的值。

显然， $d$的初始值为0。

那么考虑$d$的差分数组，记为$B$ ，那么我们只需要求出$B$的前缀和再加上$A[i]$，就能得到$A{}'[i]$，也就是修改后的值。

这时我们的树状数组c维护的就是$B$的前缀和了，修改区间$\left [ x,y \right ]$的操作只需要$update(x,k) update(y+1,-k)$ 即可

查询修改后的元素值就是 $sum(i) + A[i]$

究极进化：区间修改后的区间查询

这次我们考虑对原数组$A$差分, 记为 $a$ 吧，那么树状数组维护的就是$a$的前缀和，也就是说 $A_{n^{}} = \sum_{i=1^{}}^{n}c_{i}$

修改操作也是和原来的一样，$update(x,k) update(y,-k) $即可那么如何查询区间和呢？

不难发现有如下表达式$\sum_{i=1}^{n}A_{i} = \sum_{i=1}^{n}\sum_{j=1}^{i}c_{j}$

观察后发现，$c[1]$出现了$n$次，$c[k]$出现了$(n-k+1)$次

所以

$\sum_{i=1}^{n}A_{i} = \sum_{i=1}^{n}(c_{i}*(n+1)-c_{i}*i)$

所以我们只需要维护两个树状数组，一个是$c[i]$ 一个是$c[i]*i$

inline void update(int i,int x){
    for(;i<=n;i+=lowbit(i))f[i]+=x;
}//更新f[i] -> c[i]
inline int sum(int *tree,int x){
    int ans = 0;
    for(;x;x-=lowbit(x))ans+=tree[x];
    return ans;
}//统一求和
inline void update1(int i,int x){
    int j = i;
    for(;i<=n;i+=lowbit(i))c[i]+=x*j; 
}//更新c[i] -> c[i] * i
int s1 = (y+1)*sum(f,y) - sum(c,y);
int s2 = x*sum(f,x-1) - sum(c,x-1);
printf("%d\n",s1-s2);
//求修改后区间和

看完留个赞呗逃

码农公寓