- 「数据结构详解·一」树的初步
- 「数据结构详解·二」二叉树的初步
- 「数据结构详解·三」栈
- 「数据结构详解·四」队列
- 「数据结构详解·五」链表
- 「数据结构详解·六」哈希表
- 「数据结构详解·七」并查集的初步
- 「数据结构详解·八」带权并查集 & 扩展域并查集
- 「数据结构详解·九」图的初步
- 「数据结构详解·十」双端队列 & 单调队列的初步
- 「数据结构详解·十一」单调栈
- 「数据结构详解·十二」有向无环图 & 拓扑排序
- 「数据结构详解·十三」优先队列 & 二叉堆的初步
- 「数据结构详解·十四」对顶堆
- 「数据结构详解·十五」树状数组
0. 前置知识：lowbit 运算
我们定义 lowbit ( x ) \text{lowbit}(x) lowbit(x) 为 x x x 在二进制下最低的 1 1 1 所代表的数。
如 lowbit ( 101 0 2 ) = 1 0 2 = 2 10 , lowbit ( 1110 1 2 ) = 1 2 = 1 10 \text{lowbit}(1010_2)=10_2=2_{10},\text{lowbit}(11101_2)=1_2=1_{10} lowbit(10102)=102=210,lowbit(111012)=12=110。
我们要如何计算这个东西呢？
一种通常的计算方法是 lowbit ( x ) = x & ( ( ∼ x ) + 1 ) = x & − x \text{lowbit}(x)=x\&((\sim x)+1)=x\&-x lowbit(x)=x&((∼x)+1)=x&−x，手模一下可以得到正确性。
现在你学会了计算 lowbit，下面就可以学习树状数组了！
1. 树状数组的概念
树状数组(Binary Indexed Tree, BIT, Fenwick Tree)，也称作二叉索引树，是一种维护序列信息的数据结构。所维护的序列信息和运算需要满足一定的要求：
- 可差分性：即如果知道了 a ∘ b a\circ b a∘b 和 a a a，可以推得 b b b。
- 结合律：即维护的信息所做的运算 ∘ \circ ∘ 满足 ( a ∘ b ) ∘ c = a ∘ ( b ∘ c ) (a\circ b)\circ c=a\circ(b\circ c) (a∘b)∘c=a∘(b∘c)。
在树状数组中，记 bit i \text{bit}_i biti 为区间 [ i- lowbit( i )+1, i ] \textbf{[\textit{i-}lowbit(\textit i)+1,\textit i]} [i-lowbit(i)+1,i] 的信息和。
那么，对于一个序列 a a a 的前缀信息，都被划分成了 log \textbf{log} log 块。
如图所示，底部的点是 a i a_i ai，上方的点是 bit i \text{bit}_i biti。
下面以例题具体解释树状数组的实现。
2. 例题详解
2-1. Luogu P3374 【模板】树状数组 1 / Loj 130 树状数组 1 ：单点修改，区间查询
思考一下我们修改位置 x x x 的数会影响的到的 bit i \text{bit}_i biti。
结合上图的观察，可以发现，如果我们从下往上修改，当修改的是 x x x，则下一次修改的就是 x + lowbit ( x ) x+\text{lowbit}(x) x+lowbit(x)（具体证明留给读者思考）。
而查询 ∑ i = l r a i \sum\limits_{i=l}^ra_i i=l∑rai 可以拆成 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i i=1∑rai−i=1∑l−1ai。
显然查询前缀和我们只要不断减去当前的 lowbit \text{lowbit} lowbit 即可。
修改和查询的时间复杂度都是 O ( n log n ) O(n\log n) O(nlogn)。
具体实现：
#include<bits/stdc++.h>
using namespace std;struct fwk{int n,bit[500005];void init(int i){n=i;memset(bit,0,sizeof(bit));}void add(int i,int c){for(;i<=n;i+=i&-i) bit[i]+=c;}int qry(int i){int res=0;for(;i;i-=i&-i) res+=bit[i];return res;}
}bit;int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);int n,m;cin>>n>>m;bit.init(n);for(int i=1;i<=n;i++){int x;cin>>x;bit.add(i,x);}while(m--){int op,x,y;cin>>op>>x>>y;if(op==1) bit.add(x,y);else cout<<bit.qry(y)-bit.qry(x-1)<<endl;}return 0;
}
2-2. Luogu P3368 【模板】树状数组 2 / Loj 131 树状数组 2 ：区间修改，单点查询
我们 BIT 只能单点修改啊？怎么办！
其实，只要将序列 a a a 差分成为 b b b 后（ b i = a i − a i − 1 b_i=a_i-a_{i-1} bi=ai−ai−1），就变成了单点修改 b l ← b l + x , b r + 1 ← b r + 1 − x b_{l}\gets b_l+x,b_{r+1}\gets b_{r+1}-x bl←bl+x,br+1←br+1−x，区间查询 ∑ i = 1 x b i \sum\limits_{i=1}^xb_i i=1∑xbi 了。
代码和上一题几乎是一样的，所以不再展示了。
2-3. Luogu P3372 【模板】线段树 1 / Loj 132 树状数组 3 ：区间修改，区间查询
这就不是很好做了。
首先区间查询就是 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i i=1∑rai−i=1∑l−1ai，也就是说我们只要考虑如何求一个前缀和 ∑ i = 1 x a i \sum\limits_{i=1}^xa_i i=1∑xai。
同上一题一样，将 a a a 差分得到 b b b，有这样的推导：
∑ i = 1 x a i = ∑ i = 1 x ∑ j = 1 i b j = b 1 + b 1 + b 2 + b 1 + b 2 + b 3 + ⋯ + b 1 + b 2 + b 3 + ⋯ + b x = ∑ i = 1 x ( x − i + 1 ) b i = ( x + 1 ) ∑ i = 1 x b i − ∑ i = 1 x i ⋅ b i \begin{aligned} &\sum\limits_{i=1}^xa_i\\ =&\sum\limits_{i=1}^x\sum\limits_{j=1}^ib_j\\ =&b_1+\\ &b_1+b_2+\\ &b_1+b_2+b_3+\\ &\cdots+\\ &b_1+b_2+b_3+\cdots+b_x\\ =&\sum\limits_{i=1}^x(x-i+1)b_i\\ =&(x+1)\sum\limits_{i=1}^xb_i-\sum\limits_{i=1}^xi\cdot b_i \end{aligned} ====i=1∑xaii=1∑xj=1∑ibjb1+b1+b2+b1+b2+b3+⋯+b1+b2+b3+⋯+bxi=1∑x(x−i+1)bi(x+1)i=1∑xbi−i=1∑xi⋅bi
发现前后两个和式都是可以用 BIT 维护的！
于是就做完了。代码留给读者实现。
3. 值域树状数组
也称权值树状数组，就是将值的出现情况展现在 BIT 上，类似于哈希表。
以 Luogu P1908 逆序对 为例。
题目要求 i < j i<j i<j 且 a i > a j a_i>a_j ai>aj 的二元组 ( i , j ) (i,j) (i,j) 个数。
考虑一个显然的事情：开一个桶，存放每种数的出现次数 c i c_i ci。那么当加入 a j a_j aj 时，能与 j j j 配对形成 ( i , j ) (i,j) (i,j) 的 i i i 的个数就是 ∑ k = 1 i − 1 c k \sum\limits_{k=1}^{i-1}c_k k=1∑i−1ck。
而这个东西恰恰是可以使用 BIT 维护的！
代码也很简单，留给读者实现。
4. 二维树状数组
也称 BIT 套 BIT，也就是把 BIT 放到平面上。
以 Loj 133 二维树状数组 1：单点修改，区间查询 为例。
单点修改是同理的，只要在循环外再套一层就可以。
void add(int x,int y,int d)
{for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j){bit[i][j]+=d;}}
}
区间查询同理。但是注意查询的是 ∑ i = 1 x ∑ j = 1 y a i , j \sum\limits_{i=1}^x\sum\limits_{j=1}^ya_{i,j} i=1∑xj=1∑yai,j 的信息，即二维前缀和，减一减即可。
int qry(int x,int y)
{int res=0;for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){res+=bit[i][j];}}return res;
}
int qry(int a,int b,int c,int d){return qry(c,d)-qry(c,b-1)-qry(a-1,d)+qry(c-1,d-1);}
而 Loj 134 二维树状数组 2：区间修改，单点查询 做二维差分即可。
但是，Luogu P4514 上帝造题的七分钟 / Loj 135 二维树状数组 3：区间修改，区间查询 就不是这样的了。
和一维的同理，令 b i , j = a i , j − a i − 1 , j − a i , j − 1 + a i − 1 , j − 1 b_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1} bi,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1 后推一个式子：
∑ i = 1 x ∑ j = 1 y a i , j = ∑ i = 1 x ∑ j = 1 y ∑ p = 1 i ∑ q = 1 j b p , q = ∑ i = 1 x ∑ j = 1 y ( x − i + 1 ) ( y − j + 1 ) b i , j = ∑ i = 1 x ∑ j = 1 y ( ( x + 1 ) ( y + 1 ) − ( x + 1 ) j − ( y + 1 ) i + i ⋅ j ) b i , j = ( x + 1 ) ( y + 1 ) ∑ i = 1 x ∑ j = 1 y b i , j − ( x + 1 ) ∑ i = 1 x ∑ j = 1 y j ⋅ b i , j − ( y + 1 ) ∑ i = 1 x ∑ j = 1 y i ⋅ b i , j + ∑ i = 1 x ∑ j = 1 y i ⋅ j ⋅ b i , j \def\s{\sum\limits} \begin{aligned} &\s_{i=1}^x\s_{j=1}^ya_{i,j}\\ =&\s_{i=1}^x\s_{j=1}^y\s_{p=1}^i\s_{q=1}^jb_{p,q}\\ =&\s_{i=1}^x\s_{j=1}^y(x-i+1)(y-j+1)b_{i,j}\\ =&\s_{i=1}^x\s_{j=1}^y((x+1)(y+1)-(x+1)j-(y+1)i+i\cdot j)b_{i,j}\\ =&(x+1)(y+1)\s_{i=1}^x\s_{j=1}^yb_{i,j}-(x+1)\s_{i=1}^x\s_{j=1}^yj\cdot b_{i,j}-(y+1)\s_{i=1}^x\s_{j=1}^yi\cdot b_{i,j}+\s_{i=1}^x\s_{j=1}^yi\cdot j\cdot b_{i,j} \end{aligned} ====i=1∑xj=1∑yai,ji=1∑xj=1∑yp=1∑iq=1∑jbp,qi=1∑xj=1∑y(x−i+1)(y−j+1)bi,ji=1∑xj=1∑y((x+1)(y+1)−(x+1)j−(y+1)i+i⋅j)bi,j(x+1)(y+1)i=1∑xj=1∑ybi,j−(x+1)i=1∑xj=1∑yj⋅bi,j−(y+1)i=1∑xj=1∑yi⋅bi,j+i=1∑xj=1∑yi⋅j⋅bi,j
于是开 4 4 4 个 BIT 分别维护 b i , j , i ⋅ b i , j , j ⋅ b i , j , i ⋅ j ⋅ b i , j b_{i,j},i\cdot b_{i,j},j\cdot b_{i,j},i\cdot j\cdot b_{i,j} bi,j,i⋅bi,j,j⋅bi,j,i⋅j⋅bi,j 即可。
5.巩固练习
事实上，BIT 还有很多应用，如维护不可差分的信息等。但这些通常是用其他数据结构平替的，故不在此继续做阐述。感兴趣的读者可以自行了解。
- 上述未给出代码的例题
- Luogu P2068 统计和
- Luogu P2357 守墓人
- Luogu P1774 最接近神的人
- Luogu P1637 三元上升子序列