树状数组
前置知识
学习树状数组之前，最好先了解下面这些内容：
- 前缀和与差分；
- 二进制与位运算；
树状数组的代码非常短，核心操作甚至只有几行。不过代码短不代表它很好理解，特别是第一次看到x += x & -x和x -= x & -x时，很容易产生一种“它为什么能这样跳”的疑问。
所以这篇文章不会只给出一个模板，而是从树状数组到底解决了什么问题开始，把lowbit、节点所维护的区间、修改和查询的方向一步一步说明白，然后再继续学习差分树状数组、双树状数组、离散化、逆序对和动态第$k$小。
为什么需要树状数组？
先考虑一个很普通的问题：给定一个长度为$n$的数组，需要进行下面两种操作。
- 将第$x$个数增加$k$；
- 查询区间$[l,r]$的元素和。
如果直接使用普通数组，那么修改一次只需要$O(1)$，但是查询区间和需要从$l$一直加到$r$，复杂度为$O(n)$。
如果使用前缀和数组：
$$
s_i=\sum_{j=1}^{i}a_j
$$
查询区间和确实只需要：
$$
\sum_{i=l}^{r}a_i=s_r-s_{l-1}
$$
复杂度降到了$O(1)$。但是修改$a_x$以后，$s_x,s_{x+1},\dots,s_n$都要跟着改变，一次修改又变成了$O(n)$。
| 方法 | 单点修改 | 区间求和 |
|---|---|---|
| 普通数组 | $O(1)$ | $O(n)$ |
| 前缀和 | $O(n)$ | $O(1)$ |
| 树状数组 | $O(\log n)$ | $O(\log n)$ |
普通数组把时间全花在查询上，前缀和把时间全花在修改上。树状数组选择了一个折中的办法：它不保存所有前缀和，而是保存许多段长度不同的区间和，因此修改和查询都可以在$O(\log n)$内完成。
lowbit
树状数组最核心的函数叫lowbit：
1 | int lowbit(int x) { return x & -x; } |
lowbit(x) 函数表示$x$的二进制表示中，最低位的$1$以及它后面的所有$0$所组成的数，也就是$x$能够整除的最大二的幂。
例如：
| $x$ | 二进制 | lowbit(x) | 十进制结果 |
|---|---|---|---|
| $6$ | $0110$ | $0010$ | $2$ |
| $8$ | $1000$ | $1000$ | $8$ |
| $10$ | $1010$ | $0010$ | $2$ |
| $12$ | $1100$ | $0100$ | $4$ |
为什么x & -x能够取出最低位的$1$？
计算机使用补码表示负数，$-x$可以看作对$x$按位取反后再加$1$。这个过程中，$x$最低位的$1$右边全部都是$0$，取反加一以后，这一位及其右边会与原数保持可以相交的形式；而更高位全部无法同时为$1$。两者按位与以后，最后只剩下最低位的$1$。
以$x=12$为例：
1 | x = 0000 1100 |
所以lowbit(12)=4。
如果现在感觉补码这一部分稍微有点绕，也不影响后面使用。先记住：
lowbit(x) 的结果就是$x$在树状数组中所管理区间的长度。
树状数组中每个位置存了什么？
设原数组为$a$，树状数组为$tree$。tree[x] 节点并不是简单地保存$a_x$，它保存的是下面这段区间的和：
$$
tree[x]=\sum_{i=x-\operatorname{lowbit}(x)+1}^{x}a_i
$$
换句话说，tree[x] 节点维护的区间为：
$$
[x-\operatorname{lowbit}(x)+1,x]
$$
当$n=8$时，各节点管理的范围如下：
| 节点 | lowbit | 管理区间 | 保存的内容 |
|---|---|---|---|
| tree[1] | $1$ | $[1,1]$ | $a_1$ |
| tree[2] | $2$ | $[1,2]$ | $a_1+a_2$ |
| tree[3] | $1$ | $[3,3]$ | $a_3$ |
| tree[4] | $4$ | $[1,4]$ | $a_1+a_2+a_3+a_4$ |
| tree[5] | $1$ | $[5,5]$ | $a_5$ |
| tree[6] | $2$ | $[5,6]$ | $a_5+a_6$ |
| tree[7] | $1$ | $[7,7]$ | $a_7$ |
| tree[8] | $8$ | $[1,8]$ | $a_1+\cdots+a_8$ |
虽然它叫“树状数组”，代码中却不需要真的建立一棵树。父子关系和每个节点管理的范围都已经隐藏在下标的二进制结构中，我们只需要一个数组就能存下整棵树。
图片占位 2：长度为 8 的树状数组节点管辖区间图
单点修改
假设我们要让$a_3$增加$k$。
首先，tree[3] 节点维护$[3,3]$，其中包含$a_3$，所以需要修改这个节点。
接着，tree[4] 节点维护$[1,4]$，其中也包含$a_3$，所以同样需要修改。
最后，tree[8] 节点维护$[1,8]$，仍然包含$a_3$，所以也需要修改。
整个修改路径为：
$$
3\rightarrow4\rightarrow8
$$
从当前节点跳到下一个需要修改的节点，只需要：
1 | x += lowbit(x); |
所以单点增加的代码如下：
1 | void add(int x, i64 k) { for (; x <= n; x += lowbit(x)) tree[x] += k; } |
每次跳转都会让下标的某个二进制位发生变化，所管理的区间越来越大。最多跳$O(\log n)$次，就会超过$n$，因此单点修改的时间复杂度为$O(\log n)$。
图片占位 3：修改位置 3 时的向上更新路径
前缀和查询
接着考虑如何查询$a_1+a_2+\cdots+a_7$。
tree[7] 节点管理$[7,7]$，先把它加入答案。剩下需要查询$[1,6]$。
tree[6] 节点管理$[5,6]$，再把它加入答案。剩下需要查询$[1,4]$。
tree[4] 节点刚好管理$[1,4]$，加入答案以后查询结束。
于是：
$$
\sum_{i=1}^{7}a_i=tree[7]+tree[6]+tree[4]
$$
查询路径为：
$$
7\rightarrow6\rightarrow4\rightarrow0
$$
从当前右端点删去已经统计的区间，只需要：
1 | x -= lowbit(x); |
完整代码如下：
1 | i64 prefix(int x) { i64 ans = 0; for (; x; x -= lowbit(x)) ans += tree[x]; return ans; } |
同样，前缀和查询的时间复杂度为$O(\log n)$。
得到了前缀和以后，区间$[l,r]$的和就是：
1 | i64 query(int l, int r) { return prefix(r) - prefix(l - 1); } |
图片占位 4：查询前缀 7 时的区间拆分图
基础模板
把上面的内容合在一起，就是最基础的树状数组模板。代码头仍然保留固定宽度整数别名，不过普通下标、循环变量和操作编号直接使用int；只有可能溢出的元素和、修改量与答案才使用i64。
1 | using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; |
这里需要特别注意：树状数组的下标必须从$1$开始。
如果对下标$0$执行修改，那么lowbit(0)=0，执行x += lowbit(x) 这一步以后，$x$仍然等于$0$，程序会直接陷入死循环。这也是树状数组最常见、同时也最好排查的错误之一。
例题与典型应用
只看模板很容易产生“好像会了”的错觉。下面把五道题放在同一个章节里，从普通树状数组一路走到差分、双树状数组、逆序对和第$k$小，正好串起最常见的几种用法。
例题一：AtCoder Practice2 B - Fenwick Tree
题目链接：AtCoder Practice2 B - Fenwick Tree
题目要求维护一个长度为$n$的数组，支持下面两种操作：
- 0 p x：令$a_p\gets a_p+x$；
- 1 l r：查询$\sum_{i=l}^{r-1}a_i$。
这就是标准的“单点增加、区间求和”。唯一需要注意的是，题目的数组下标从$0$开始，而我们写的树状数组从$1$开始。
因此原数组的$a_p$应当放进树状数组的$p+1$位置。
题目查询的是左闭右开区间$[l,r)$。其中包含原数组的前$r$个数，减去前$l$个数，所以答案为：
1 | prefix(r) - prefix(l) |
而不是常见的prefix(r)-prefix(l-1) 这种写法。这里并不是前缀和公式变了，而是题目使用了从$0$开始的下标和左闭右开区间。
点击展开完整代码
1 | /* Fufffh */ |
$O(n)$建树
上面的代码通过$n$次add完成初始化，复杂度为$O(n\log n)$。树状数组也可以在线性时间内建树。
先把$a_i$加入tree[i] 节点，再把这个节点的值整体交给它的直接父节点：
1 | for (int i = 1; i <= n; i++) { |
因为从左到右枚举到$i$时，tree[i] 节点所管理区间内的值已经全部收集完成，可以直接把整段区间和加入父节点。
不过比赛中大多数基础题的$O(n\log n)$初始化已经足够，而且不容易写错。线性建树知道即可，不必为了少一个对数强行增加出错的机会。
例题二：洛谷 P3368 树状数组 2
题目链接：洛谷 P3368 树状数组 2
题目需要支持：
- 将区间$[l,r]$中的每个数增加$k$；
- 查询第$x$个数现在的值。
基础树状数组支持的是单点增加，而这里需要区间增加。看起来操作正好反过来了，但是加入差分数组以后，问题就会重新变成树状数组熟悉的样子。
差分数组
定义：
$$
d_i=a_i-a_{i-1}
$$
其中规定$a_0=0$，那么：
$$
a_x=d_1+d_2+\cdots+d_x
$$
也就是说，原数组中的单点值，正好是差分数组的前缀和。
如果要让区间$[l,r]$全部增加$k$，区间内部相邻两个数都增加了$k$，它们之间的差不会改变。真正发生变化的只有左右两个端点：
$$
d_l\gets d_l+k
$$
$$
d_{r+1}\gets d_{r+1}-k
$$
于是一次区间修改被转换成了两次单点修改。查询$a_x$时，只需要查询差分数组的前缀和。
图片占位 5：差分数组完成区间增加的端点变化图
初始化
读入原数组时，可以直接计算相邻两项的差，并把差分值加入树状数组：
1 | i64 lst = 0; |
区间修改与单点查询
1 | void rangeAdd(int l, int r, i64 k) { add(l, k); add(r + 1, -k); } |
当$r=n$时，add(r+1,-k) 这次修改会从$n+1$开始。因为add 函数中的条件是x<=n，所以不会进入循环，也就不需要单独特判。
点击展开完整代码
1 | /* Fufffh */ |
例题三：洛谷 P3372 线段树 1
题目链接：洛谷 P3372 线段树 1
题目的名字虽然叫“线段树 1”，但是它同样可以使用树状数组完成。需要支持：
- 将区间$[l,r]$中的每个数增加$k$；
- 查询区间$[l,r]$的元素和。
P3368通过差分数组实现了区间修改，但是只能查询一个位置。现在如果还想求区间和，就需要继续推导原数组的前缀和。
仍然令：
$$
d_i=a_i-a_{i-1}
$$
那么原数组前$x$项的和为：
$$
\begin{aligned}
S_x
&=a_1+a_2+\cdots+a_x\
&=d_1+(d_1+d_2)+\cdots+(d_1+d_2+\cdots+d_x)
\end{aligned}
$$
观察每个$d_i$出现的次数：$d_1$出现$x$次，$d_2$出现$x-1$次，$d_x$只出现一次。因此：
$$
S_x=xd_1+(x-1)d_2+\cdots+d_x
$$
把它整理一下：
$$
\begin{aligned}
S_x
&=\sum_{i=1}^{x}(x-i+1)d_i\
&=(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i
\end{aligned}
$$
这里出现了两个前缀和：
- $\sum d_i$；
- $\sum i\cdot d_i$。
所以我们建立两棵树状数组：
- tree1维护$d_i$；
- tree2维护$i\cdot d_i$。
于是原数组的前缀和可以写成：
1 | i64 sum(int x) { return (x + 1) * prefix(tree1, x) - prefix(tree2, x); } |
图片占位 6：双树状数组前缀和公式推导图
如何修改两棵树状数组？
当差分数组的$d_x$增加$k$时：
- tree1[x] 的值对应增加$k$；
- tree2[x] 的值对应增加$x\cdot k$。
1 | void modify(int x, i64 k) { add(tree1, x, k); add(tree2, x, k * x); } |
区间$[l,r]$增加$k$，仍然只修改差分数组的两个端点：
1 | void rangeAdd(int l, int r, i64 k) { modify(l, k); modify(r + 1, -k); } |
最终区间和为：
$$
\operatorname{sum}(l,r)=S_r-S_{l-1}
$$
点击展开完整代码
1 | /* Fufffh */ |
到这里，树状数组常见的三组操作已经全部出现：
| 修改方式 | 查询方式 | 实现方法 |
|---|---|---|
| 单点修改 | 区间查询 | 普通树状数组 |
| 区间修改 | 单点查询 | 维护差分数组 |
| 区间修改 | 区间查询 | 维护$d_i$和$i\cdot d_i$两棵树状数组 |
例题四：洛谷 P1908 逆序对
题目链接：洛谷 P1908 逆序对
对于一个序列，如果$i<j$并且$a_i>a_j$，那么$(i,j)$就是一个逆序对。题目要求统计整个序列中逆序对的数量。
最直接的做法是枚举$i,j$，复杂度为$O(n^2)$。但是$n$最大为$5\times10^5$，显然无法通过。
换一个角度统计
从左向右枚举$a_i$。当枚举到当前位置时，前面的$i-1$个数都已经加入树状数组。
记$c_i$为前面小于等于$a_i$的元素个数。前面一共有$i-1$个数，因此当前位置新产生的逆序对数量为：
$$
\operatorname{inv}_i=(i-1)-c_i
$$
这些大于$a_i$的数都位于$a_i$左侧，因此它们分别和当前$a_i$组成一个逆序对。
这里树状数组维护的不再是“原数组每个位置的值”，而是：
每一种数值已经出现了多少次。
当树状数组维护出现次数时，查询某个值对应位置的前缀和，就表示“小于等于这个值的数字出现了多少个”。这种把数值当成下标、维护出现次数的树状数组，通常也叫权值树状数组。
离散化
题目中的$a_i$最大可以达到$10^9$，我们不可能开一个大小为$10^9$的树状数组。
注意到这里并不关心数值之间具体相差多少，只关心它们的大小关系。因此可以排序去重，将每个数替换成它在所有不同数值中的排名，这个过程叫离散化。
例如：
1 | 原数组：5 2 6 2 1 |
$1,2,5,6$之间原本的距离消失了，但是它们的大小关系完全没有改变，所以逆序对数量也不会改变。
对于每个$a_i$，可以使用lower_bound找到排名：
1 | int rank = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; |
这里最后加$1$，仍然是因为树状数组不能使用下标$0$。
重复数字的处理
逆序对的条件是严格大于，而不是大于等于。所以前面与$a_i$相等的数不能计入答案。
prefix(rank) 的结果是小于等于$a_i$的数量，用已经处理的总数$i-1$减去它，剩下的才全部严格大于$a_i$：
1 | ans += (i - 1) - prefix(rank); |
一定要先统计答案，再把当前数加入树状数组。否则当前$a_i$也会被算进“前面已经出现的数”中。
图片占位 7：离散化后扫描并统计逆序对的过程图
点击展开完整代码
1 | /* Fufffh */ |
逆序对也可以从右向左统计。此时树状数组中存放的是当前位置右边的数，当前$a_i$产生的逆序对数量就是右边严格小于它的数量：
1 | ans += prefix(rank - 1); |
两种方向的本质完全相同。遇到类似计数题时，可以根据“不等号方向”和“哪一侧更方便统计”选择扫描方向。
例题五：Codeforces 1354D Multiset
题目链接：Codeforces 1354D - Multiset
题目需要维护一个可重复集合，操作分为两种：
- 插入数字$x$；
- 删除集合中第$k$小的数字。
所有数字都在$[1,n]$范围内。可以让tree[x] 的值表示数字$x$的出现次数，插入$x$就是：
1 | add(x, 1); |
假设集合为：
1 | 1 1 2 4 4 5 7 |
那么频率前缀和的意义如下：
| $x$ | $\operatorname{prefix}(x)$ | 意义 |
|---|---|---|
| $1$ | $2$ | 有$2$个数小于等于$1$ |
| $2$ | $3$ | 有$3$个数小于等于$2$ |
| $4$ | $5$ | 有$5$个数小于等于$4$ |
第$k$小的数，就是满足下面条件的最小$x$：
$$
\operatorname{prefix}(x)\ge k
$$
因为频率前缀和一定单调不减，可以对$x$进行二分。每次二分又需要一次$O(\log n)$的树状数组查询，总复杂度为$O(\log^2 n)$。
普通数据下这样已经能用，但是这道题的$n,q$都可能达到$10^6$，时间限制和内存限制也比较紧。我们可以直接在树状数组内部进行倍增，将寻找第$k$小优化到$O(\log n)$。
树状数组上倍增
我们从不超过$n$的最大二的幂开始尝试，逐步缩小步长。
维护：
- pos：当前确定的下标；
- sum：当前位置之前已经累计的频率；
- t：本轮尝试向右跳的距离。
如果跳到nxt以后，累计频率仍然小于$k$，说明第$k$小一定还在右边，可以接受这次跳转：
1 | if (nxt <= n && sum + tree[nxt] < k) { |
这里直接使用tree[nxt]，而不是重新调用一次prefix(nxt)。原因是我们始终按照二的幂从大到小试探，并且pos表示已经完整跳过的前缀；此时tree[nxt]恰好对应紧接在这段前缀后面的一个树状数组区间。接受跳转，相当于把这一整段的频率并入sum。所有步长总共只会尝试$O(\log n)$次，这正是它比“外层二分、内层查询”更快的地方。
循环结束时，pos是“前缀和仍然小于$k$的最后一个位置”，因此pos+1就是第一个前缀和大于等于$k$的位置。
1 | int kth(int k) { |
这里的判断必须是严格小于$k$。如果写成小于等于$k$，就会跳过第一个前缀和恰好等于$k$的位置。
找到第$k$小的数以后，将其出现次数减一即可完成删除：
1 | int pos = kth(k); |
图片占位 8：频率前缀和中寻找第 k 小的阶梯图
点击展开完整代码
1 | /* Fufffh */ |
这道题再次体现了权值树状数组的特点：下标代表数值，树状数组中保存的是出现次数，前缀和代表排名。
如果数值范围很大，也可以先把所有可能出现的数离散化，再维护对应排名的出现次数。不过在线处理时，必须保证需要离散化的值能够提前读到；如果数据真正动态产生，就需要考虑平衡树等其他数据结构。
总结与常见问题
树状数组能维护什么？
最常见的树状数组维护的是加法和，因为区间和可以由两个前缀和相减得到：
$$
sum(l,r)=sum(r)-sum(l-1)
$$
类似地，异或也有可逆性质，所以树状数组可以维护区间异或。
树状数组也可以在某些限制下维护前缀最大值或最小值，但是修改通常需要满足单调性。例如某个位置只会不断变大时，可以维护前缀最大值；如果一个位置既可能变大又可能变小，原有节点中的最大值可能失效，此时普通树状数组就很难处理。
简单地说：
- 单点修改、前缀查询以及可以通过两个前缀答案作差得到的区间信息，优先考虑树状数组；
- 需要任意区间最值、复杂区间修改、维护多种信息时，线段树通常更加合适；
- 需要维护动态有序集合，而值域较小或可以离散化时，可以考虑权值树状数组；
- 需要真正动态的键值、前驱后继、分裂合并等操作时，应考虑平衡树。
树状数组的优点是代码短、常数小、占用空间少；缺点也很明显，它能维护的信息不如线段树灵活。没有哪一种数据结构能够包办所有问题，重要的是先看清题目需要的修改和查询是什么。
常见错误
1. 使用下标$0$
1 | add(0, k); |
会因为lowbit(0)=0陷入死循环。外部下标从$0$开始时，要先转换成树状数组内部的$1$下标。
2. 忘记使用i64
单个$a_i$没有超过int，不代表区间和、逆序对数量或者$i\cdot d_i$不会超过int。本文统一把这些可能溢出的量声明为i64，不要让正确的思路最后输在数据范围上。
3. 把赋值修改直接当成增加修改
add(x,k) 的含义是$a_x\gets a_x+k$。
如果题目要求把$a_x$修改为$k$，需要先计算变化量：
1 | add(x, k - a[x]); |
4. 区间边界写错
对于从$1$开始的闭区间$[l,r]$：
1 | prefix(r) - prefix(l - 1); |
对于从$0$开始的左闭右开区间$[l,r)$，转换到本文的内部下标后是：
1 | prefix(r) - prefix(l); |
写代码前先确定题目的下标和区间形式，不要把两套公式混在一起。
5. 逆序对把相等元素算进去
如果要求$a_i>a_j$，相等元素不能计入。正序扫描时查询“小于等于当前值”的数量，倒序扫描时查询“严格小于当前值”的数量，二者不要混淆。
6. 第$k$小的判断条件写成小于等于
我们要寻找第一个前缀和大于等于$k$的位置，所以倍增时只能跳过前缀和严格小于$k$的位置：
1 | sum + tree[nxt] < k |
7. 多组测试忘记清空
如果题目有多组数据，上一组的树状数组不会自己消失。可以使用fill或memset清空实际使用的范围，也可以为每组数据重新建立vector。
复杂度总结
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单点增加 | $O(\log n)$ | $O(n)$ |
| 前缀和查询 | $O(\log n)$ | $O(n)$ |
| 区间和查询 | $O(\log n)$ | $O(n)$ |
| 差分区间增加 | $O(\log n)$ | $O(n)$ |
| 双树状数组区间增加、区间查询 | $O(\log n)$ | $O(n)$ |
| 权值树状数组插入、删除 | $O(\log n)$ | $O(n)$ |
| 树状数组倍增求第$k$小 | $O(\log n)$ | $O(n)$ |