树状数组(基础)

树状数组

简介

树状数组是一种数据结构，非常适用于数列中点以及区间的查询或更新，例如求区间的和，可以直接扫描一遍这个区间，复杂度是$O(n)$,如果要操作$M$次呢？那么最坏情况下复杂度变成了$O(M\ast N)$，当数据规模十分庞大的时候是很划不来的，如果使用树状数组，复杂度会变成$O(M\ast log(n))$

原理

首先来看一张图

---

现在有$8$个数，存在数组$A$中，同时有另外一个数组$C$，表示我们要维护的树状数组，$C$中的每个点维护了一段或一个点的信息，那么数组A分别对应图上树的8个叶子结点，而图上标记数字的，表示数组$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]$

那么数组A和C之间一定存在某种关系，让我们在对数组A进行区间或点的操作时，可以转换到数组C上，通过树的关系来减少运算次数，怎么操作呢? 首先观察数组$C$和$A$的关系 不难，当下标为奇数的时候，$C[i]=A[i]$，当下标为2的幂数的时候 $C[i]=\sum _{j=1}^i{A}_j$(即前缀和)，当下标为偶数的时候，$C[i]=A[i-1]+A[i]$，如果把每一个$C$中加进去的$A$的数量，叫做这一段的长度，那么对于每一个$C[i]$有什么方法可以快速获得段长吗? 那就要考虑二进制 对于下标$1-8$，二进制的变化如下（假设只考虑一个字节） $00000001$ （1） $00000010$ （2） $00000011$ （1） $00000100$ （3） $00000101$ （1） $00000110$ （2） $00000111$ （1） $00001000$ （4） 其中后面（）内部的数字，表示从右往左二进制1第一次出现的位置，很显然，这就是要找的段长，从$C[1]-C[8]$段长分别为$12131214$，那么这个段长就是取二进制的从右往左第一个1的位置，这个操作叫$lowbit$

lowbit(x) = (x&(-x))//因为负数是通过取反+1来实现的 /* 例如 8 00001000 11110111 + 1 = 11111000 相与得00001000 转换为10进制为8，说明C[8]维护的段长是8 */

通过$lowbit$就可以快速获取段长，有了这个操作就可以很方便实现操作了

---

1、单点修改、区间查询

单点修改： 如果要修改数组中某一个点的值，那么在树状数组C中必须要修改所有包含该点的所有点的信息，例如对于$A[1]+4$，那么$C$中所有包含$A[1]$的点都要加4，其中有1,2,4,8，可以通过不断取$lowbit$的操作来实现，更新数组$C$ for(int i = x; i <= n; i+=lowbit(i))//x为1，i变化从1,2,4,8 c[i] += 4; 区间查询，如果要求某段区间$[l,r]$的和，因为$C$中记录了很多段的信息，首先考虑求$[1,r]$ 肯定不能直接求和$C[1]$到$C[r]$，这样会计算重复，那么还是通过段长来计算，每统计一次$C[i]$，下次统计的时候为了避免重复加就减去当前段长，直到为0，比如求$[1,8]$ $ans+=C[i](i=8)$（当前段长为8） $i-=8$ 结束计算 $ans=C[8]$ 如果求[1,7] $ans+=C[i](i=7)$（当前段长为1） $i-=1$ $ans+=C[i](i=6)$（当前段长为6） $i-=2$ ··· $i-=4$（最后i为0） 结束计算 $ans=C[7]+C[6]+C[4]$ 只需计算3次即可,不过这种方式会一直计算下标为0的时候 因此如果求$[l,r]$的和可以转换成$[1,r]-[1,l-1]$

代码如下

//单点修改、区间查询 #define lowbit(x) (x&(-x)) #define ll long long #define M 100005 ll n, m, c[M]; inline ll read() { //快读 ll x = 0; bool flag = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') flag = 1; c = getchar();} while(c >= '0' && c <= '9'){x = x*10+c-48; c = getchar();} if(flag) x = -x; return x; } void change(int x, int d) { //修改所有包含x的信息 for(int i = x; i <= n; i+=lowbit(i)) c[i] += d; } ll query(int x) { //查询,求[1,x]的和，如果要求和[l,r]，则应该query(r)-query(l-1) if(x == 0) return 0; ll ret = 0; for(int i = x; i; i -= lowbit(i)) ret += c[i]; return ret; } int main() { n = read(), m = read(); //n个数，m次操作 for(int i=1;i<=n;i++) change(i,read());//边读，边更新树状数组 }

---

2、区间修改、单点查询

区间修改： 如果要对某个区间的全部加或者减，那么应该如何操作呢？ 直接去加或者减肯定是不行的，我们可以考虑记录在这个区间内，加减的状态。 假设有一列数 $15423$ 分别存在$A[1]-A[5]$中 此时数组$C[1]-C[5]$ 分别是$00000$ 比如对$[2,4]$区间全部加$2$，那么我们只对数组$C$做操作还是每次减去段长 那么$C[4]+2$，同样要对区间[1,2-1]执行相反操作，也就是$+(-2)$ 此时数组$C[1]-C[5]$ 分别是$-20020$ 假设要查询第三个点的值，那么应该从$C[3]$开始，到后面的点依次加段长，加上所有的变化情况，最后加上原来的值$A[3]$ 表示出来就是$2+0+0+4=6$ 代码如下 #define lowbit(x) (x&(-x)) #define ll long long #define M 100005 ll n, m, c[M], a[M]; inline ll read() { ll x = 0; bool flag = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') flag = 1; c = getchar();} while(c >= '0' && c <= '9'){x = x*10+c-48; c = getchar();} if(flag) x = -x; return x; } void add(int x, int dis) { //从1到X的区间全部加dis,如果对区间[l,r]所有值加上d,则应该add(r,d),add(l-1,-d) for(int i = x; i; i -= lowbit(i)) c[i] += dis; } ll query(int x) { //查询第x个数的值 if(x == 0) return 0; ll res = 0; for(int i = x; i <= n; i += lowbit(i)) //把所有的变化状态加进去 res += c[i]; return res + a[x]; //加上初值 } int main () { n = read(), m = read(); for(int i = 1; i <= n; i++) a[i] = read(); }