树状数组是一种基于二进制拆分的思想，用来动态维护序列的前缀和的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。树状数组的基本操作：1. 修改序列中的一个数。2. 查询序列前缀和。
基本思想
树状数组是一种基于二进制拆分的思想，用来动态维护序列的前缀和的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。
树状数组的基本操作：
- 修改序列中的一个数。
- 查询序列前缀和。
$lowbit(x)$ 表示将 x 写成二进制表示后，最低位的 1 所代表的数值，如 $10 = (1010)_2 , lowbit(10)=(10)_2=2$
以下是 $lowbit(x)$ 的求法，具体证明可参见 《算法竞赛进阶指南》 0x01 二进制 章节。
1 |
对于原序列 $a[n]$，树状数组用一个数组 $c[n]$，其中，$c[i]$ 表示以 $i$ 结尾长度为 $lowbit(i)$ 的区间和，即区间 $[i-lowbit(i)+1,i]$。
这时如果把整个数组视作一个树型结构（如下图，图来自《算法竞赛进阶指南》），则有以下性质：
- 每个节点表示以这个节点为根的子树中所有节点的和。
- 每个节点有 $lowbit(i)$ 个子节点，其中 $i$ 表示这个节点的编号。
- 每个节点的父节点是 $i+lowbit(i)$，其中 $i$ 表示这个节点的编号。
可以发现，树的深度是 $O(\log n)$，所以树状数组的两种基本操作的时间复杂度都是 $O(\log n)$。
代码模板
树状数组与逆序对
如果把树状数组当作一个桶使用，则可以用树状数组进行求逆序对等操作。
具体地，因为树状数组可以查询前缀和，所以可以查询比某个数小的数量，据此可统计逆序对数目。
例题：P1908 逆序对 - 洛谷，代码见代码模板-树状数组。值得注意的是，通常在值域较大的情况下，使用树状数组求逆序对需要对数据进行离散化，可以参考 【基础算法】离散化 学习笔记。
如果再对当桶使用的树状数组进行拓展，即权值树状数组，可实现一些平衡树的操作，见拓展阅读。
关于逆序对的应用，再举一个例题： 洛谷 P1637 三元上升子序列 - Solution。
使用树状数组求逆序数的另一个应用是组合数学里，求排列的字典序排名，即康托展开，详见 【组合数学】康托展开 学习笔记。
树状数组与差分
朴素的前缀和区间查询和单点修改的时间复杂度分别是 $O(1)$， $O(n)$。
树状数组可以将其优化为 $O(\log n)$，$O(\log n)$。
朴素的差分单点查询和区间修改的时间复杂度分别是 $O(n)$， $O(1)$。
树状数组同样可以将其优化为 $O(\log n)$，$O(\log n)$。
代码实现见 代码模板-树状数组，可以在 P3368 【模板】树状数组 2 - 洛谷测试。
考虑区间查询，有：$\sum_{i=1}^x a[i]$
而差分（$b[i]$是差分数组）有： $a[i]=\sum_{j=1}^i b[i]$
考虑每一个 $b[i]$ 被求和的次数（如图，图来自《算法竞赛进阶指南》），化简一下式子：
$$
\sum_{i=1}^x \sum_{j=1}^i b[i] = \sum_{i=1}^x (x-i+1) * b[i] = \sum_{i=1}^x (x+1) b[i] - ib[i] = \newline (x+1) \sum_{i=1}^x b[i] - \sum_{i=1}^x i*b[i]
$$
用树状数组分别维护 $b[i]$ 和 $i*b[i]$ 即可维护上面式子，区间查询和区间修改的时间复杂度都是 $O(\log n)$。
代码实现见 [[代码模板-树状数组#区间修改 + 区间查询（差分 + 维护 i·b[i]）]]，可以在 #132. 树状数组 3 ：区间修改，区间查询 - 题目 - LibreOJ 进行练习测试。
参考资料 && 拓展阅读 && 推荐题目
- 《算法竞赛进阶指南》，李煜东著，0x42 树状数组
- AcWing 算法提高课 4.2 树状数组
- 洛谷日报 #416 [5k_sync_closer] 浅谈权值树状数组及其扩展
推荐题目：
- AcWing 241. 楼兰图腾 提示：树状数组求逆序对+组合计数
- AcWing 244. 谜一样的牛 提示：树状数组+二分/倍增
- AcWing 260. 买票
- 洛谷题单 CMの树状数组