浅谈树状数组

## 写在前面 由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。~~喷轻点~~ 这次我将会讲的是树状数组，目测难度普及~提高，淼淼淼。~~毕竟我还是普及蒟蒻~~ 你以为我会先讲树状数组吗？ ~~会的~~ # $\text{Part 0}$ 前置芝士 ## ~~0.数组~~ ## 1.补码 ~~初赛应该学过~~ 众所周知，计算机的数据存储方式是用二进制存储的。 原来的编码叫做原码 取反后叫反码 而反码 $+1$ 就是补码 补码就是十进制下的相反数 举个栗子 ~~出门左转炒锅~~ $a=5$，二进制表示为 $0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0101$，反码为 $1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1010$，补码为 $1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011$，意为 $-5$ 好像只有这一个…… # $\text{Part 1}$ 引入 > 给你一个序列，维护两个操作：1.区间求和；2.单点增加。 对于这道题有什么思路呢？~~无~~ ~~暴力~~ 用前缀和 用数组存起来前缀和，每次修改就把修改的点以及之后的所有的前缀和都加上 $k$，询问就直接输出前缀和的差。 询问 $O(1)$，修改 $O(n-k)$，空间复杂度 $O(n)$。 # $\text{Part 2}$ 基本介绍 ### 辟谣：树状数组不是树！！！是数组！！！~~树一样的数组~~ >树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 这种数据结构（算法）并没有C++和Java的库支持，需要自己手动实现。在Competitive Programming的竞赛中被广泛的使用。树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。 $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$——百度百科《树状数组》 它的查询和修改的时间复杂度都是 $\log(n)$，常数比隔壁线段树少得多…… 空间复杂度则为 $O(n)$，实实切切的 $O(n)$，一点常数都没有……~~吊打隔壁线段树~~ # $\text{Part 3}$ 树状图和 $lowbit$ 大家都知道二叉树吧，它们长成这样：  变个型，树状图是这样的：  ~~偷百度百科的图~~ 设原数组 $a$，树状数组 $tree$ 有如下关系： | $tree[1]=a[1]$ | | :---------- | | $tree[2]=a[1]+a[2]$ | | $tree[3]=a[3]$ | | $tree[4]=a[1]+a[2]+a[3]+a[4]$ | | $tree[5]=a[5]$ | | $tree[6]=a[5]+a[6]$ | | $tree[7]=a[7]$ | | $tree[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]$ | 有个\*\*关系啊？？！！ 我们将它转换为二进制： | $tree[0001]=a[0001]$ | | :---------- | | $tree[0010]=a[0001]+a[0010]$ | | $tree[0011]=a[0011]$ | | $tree[0100]=a[0001]+a[0010]+a[0011]+a[0100]$ | | $tree[0101]=a[0101]$ | | $tree[0110]=a[0101]+a[0110]$ | | $tree[0111]=a[0111]$ | | $tree[1000]=a[0001]+a[0010]+a[0011]+a[0100]+a[0101]+a[0110]+a[0111]+a[1000]$ | ~~还是没有什么规律啊？？！！~~ 设 $lowbit(n)$ 表示二进制下最低位的 $1$ 所对应的值，如 $lowbit(4)=4$，$lowbit(7)=1$ 则$tree[n]=\sum_{i=n-lowbit(n)+1}^{n} a[i]$ 那么怎么求 $lowbit(n)$ 呢？ 举个栗子：$6=(0110)_{2},-6=(1010)_2,lowbit(6)=(0010)_2=2$ 怎么样？看出什么了吗？ $$\color{red}\Large lowbit(n)=n\&(-n)$$ 这是树状数组的核心，必记。 # $\text{Part 4}$ 单点修改以及区间查询 让我们再回顾一下这两个式子： $$tree[n]=\sum_{i=n-lowbit(n)+1}^{n} a[i],lowbit(n)=n\&(-n)$$ 以及这张图片：  于是我们考虑单点修改 我们修改 $a$ 数组的一个点的时候，会影响到 $tree$ 数组的一定范围，那么我们就需要把影响到的 $tree$ 数组也修改一下，我们发现: 当我们修改 $a[1]$ 时，会影响 $tree[1]$、 $tree[2]$、$tree[4]$、$tree[8]$； 当我们修改 $a[2]$ 时，会影响 $tree[2]$、$tree[4]$、$tree[8]$； 当我们修改 $a[3]$ 时，会影响 $tree[3]$、$tree[4]$、$tree[8]$…… 换成二进制： 当我们修改 $a[0001]$ 时，会影响 $tree[0001]$、 $tree[0010]$、$tree[0100]$、$tree[1000]$； 当我们修改 $a[0010]$ 时，会影响 $tree[0010]$、$tree[0100]$、$tree[1000]$； 当我们修改 $a[0011]$ 时，会影响 $tree[0011]$、$tree[0100]$、$tree[1000]$…… 发现规律了吗？ ~~木有~~ 当我们修改 $a[pos]$ 时，令 $pos1=pos+lowbit(pos)$，$pos2=pos1+lowbit(pos1)$……会影响 $tree[pos]$、$tree[pos1]$、$tree[pos2]$…… 可得代码： ```cpp void add(int pos,int k) { while (pos<=n) tree[pos]+=k,pos+=lowbit(pos); } ``` 类比单点修改，我们考虑一下区间查询。 为了简化问题，我们查询 $\sum_{i=1}^{pos}a[i]$ 感觉跟单点修改有点类似……~~有吗~~ 让我们重温这幅图：  要求 $\sum_{i=1}^{3}a[i]$，发现 $\sum_{i=1}^{3}a[i]=tree[2]+tree[3]$； 要求 $\sum_{i=1}^{4}a[i]$，发现 $\sum_{i=1}^{4}a[i]=tree[4]$； 要求 $\sum_{i=1}^{5}a[i]$，发现 $\sum_{i=1}^{5}a[i]=tree[4]+tree[5]$； 要求 $\sum_{i=1}^{7}a[i]$，发现 $\sum_{i=1}^{7}a[i]=tree[4]+tree[6]+tree[7]$…… 发现规律了吗？ ~~木有~~ 当我们求 $\sum_{i=1}^{pos}a[i]$ 时，令 $pos_0=pos$，$pos_1=pos_0-lowbit(pos_0)$，$pos_2=pos_1-lowbit(pos_1)$……，$pos_{max}=pos_{max-1}-lowbit(pos_{max-1})=0$，$\sum_{i=1}^{pos}a[i]=\sum_{j=0}^{max}tree[pos_j]$…… 易得代码： ```cpp int sum(int pos) { int sum=0; while (pos!=0) sum+=tree[pos],pos-=lowbit(pos); return sum; } ``` 最简单的是求 $\sum_{i=l}^{r}a[i]$ 的值 ~~其实就是区间求和~~ 易得代码（这个是真的易得）: ```cpp int sum(int l,int r) { return sum(r)-sum(l-1); } ``` 单点修改以及区间查询结束！！！ ## 模板 [P3374 【模板】树状数组 1](https://www.luogu.org/problem/P3374) 正常的函数版： ```cpp /* Name: 树状数组 Copyright: ZXJ Author: ZXJ Description: 树状数组函数版 */ #include<cstdio> using namespace std; int n,m,arr,bz,x,y,tree[500001]; int lowbit(int k) { return k&((~k)+1); } void add(int pos,int k) { while (pos<=n) tree[pos]+=k,pos+=lowbit(pos); } int sum(int pos) { int sum=0; while (pos!=0) sum+=tree[pos],pos-=lowbit(pos); return sum; } int sum(int l,int r) { return sum(r)-sum(l-1); } int main() { scanf("%d %d",&n,&m); for (register unsigned i(1);i<=n;++i) scanf("%d",&arr),add(i,arr); while (m--) { scanf("%d %d %d",&bz,&x,&y); if (bz==1) add(x,y); else printf("%d\n",sum(x,y)); } } ``` 以及~~装×可用的~~结构体版： ```cpp /* Name: 树状数组 Copyright: ZXJ Author: ZXJ Description: 树状数组结构体版 */ #include<cstdio> using namespace std; namespace BIT { const unsigned maxarray(5000001); template<typename _Tp=unsigned> struct Binary_Indexed_Tree { _Tp a[maxarray]; unsigned n; inline Binary_Indexed_Tree() { n=0; for (register unsigned i(0);i<maxarray;++i) a[i]=0; } inline Binary_Indexed_Tree(const unsigned leng) { n=leng; for (register unsigned i(0);i<=n;++i) a[i]=0; } inline _Tp operator[](const unsigned pos) { return this->a[pos]; } inline int lowbit(const int k) { return k&((~k)+1); } inline void add(unsigned pos,const _Tp value)//将第pos个数加x { while (pos<=n) a[pos]+=value,pos+=lowbit(pos); } inline _Tp sum(unsigned pos)//前pos个数的和 { _Tp ans=0; while (pos) ans+=a[pos],pos-=lowbit(pos); return ans; } inline _Tp sum(const unsigned l,const unsigned r)//求l-r区间和 { return sum(r)-sum(l-1); } }; } BIT::Binary_Indexed_Tree<int> a; int n,m,arr,bz,x,y; int main() { scanf("%d %d",&n,&m); a.n=n; for (register unsigned i(1);i<=n;++i) scanf("%d",&arr),a.add(i,arr); while (m--) { scanf("%d %d %d",&bz,&x,&y); if (bz==1) a.add(x,y); else printf("%d\n",a.sum(x,y)); } } ``` # $\text{EXPart 4}$ 树状数组可支持的其它操作 树状数组不光可以