树状数组⚓︎
较难写的数据结构：
- 线段树；
- 平衡树 (Splay)；
- 块状链表。
树状数组(Binary Indexed Tree, Fenwick tree)的特点：好写，好用。
树状数组的扩展：
- 差分；
- 差分+公式。
树状数组的难点：如何想出问题能够用树状数组求解。
树状数组的应用：
- 快速求前缀和：时间复杂度 \(O(\log n)\)；
- 修改某一个数：时间复杂度 \(O(\log n)\)。
注：对于传统的前缀和数组，求子数组和的时间复杂度为 \(O(1)\)，修改某一个数的时间复杂度为 \(O(n)\)。
树状数组的基本原理⚓︎
为方便起见，数组下标从 \(1\) 开始。设正整数 \(x\) 的二进制表示为 \(x=2^{i_k}+2^{i_{k-1}}+\cdots +2^{i_1},i_k>i_{k-1}>\cdots >i_1\)，其中 \(k\leqslant \log x\)。将 \(1\sim x\) 按如下方式分成最多 \(\log x\) 个区间：
通过预处理如上区间的子数组和，我们可以在 \(\log n\) 的时间复杂度内求出前 \(n\) 项的前缀和。
注意到 \(2^{i_1}\) 是 \(x\) 的二进制表示的最后一位 \(1\)，而 \(2^{i_2}\) 是 \(x-2^{i_1}\) 的二进制表示的最后一位 \(1\)，可以此类推。 \(\left( L,R \right]\) 的区间长度一定是 \(R\) 的二进制表示的最后一位 \(1\) 所对应的次幂。\(\left( L,R \right] =\left[ R-\mathrm{lowbit}\left( R \right) +1,R \right]\)。
\(\mathrm{lowbit}\left( n \right)\) 表示非负整数 \(n\) 在二进制表示下最低位 \(1\) 及其后面的 \(0\) 构成的数值，lowbit(x) = x & -x。
设 \(c\left[ x \right] =\mathrm{sum}\left[ x-\mathrm{lowbit}\left( x \right) +1\ \sim\ x \right]\)，设 \(x\) 二进制表示末尾有 \(k\) 个 \(0\)，则 \(c\left[ x \right]\) 表示以 \(x\) 结尾的长度为 \(2^k\) 的区间和。
图片来源：灵茶山艾府。
通过上图可以得出如下结论：
- \(c\left[ x \right]\) 保存以 \(x\) 为根的子树中叶节点值的和；
- \(c\left[ x \right]\) 负责的节点长度等于 \(\mathrm{lowbit}\left( x \right)\)；
- \(c\left[ x \right]\) 节点的父节点为 \(c\left[ x+\mathrm{lowbit}\left( x \right) \right]\)；
- 整棵树的深度为 \(\log n+1\)。
如何通过父节点找子节点？儿子的形式： \(\times \times \times \times 011\cdots 100\cdots 0\)。 \(x-1\) 的每一个 \(1\) 都对应一个儿子。每次把 \(x-1\) 每次去掉最后一个 \(1\)，去掉 \(k\) 次，就可以找到子节点。
每一个点修改完后直接影响到的区间是唯一的。
如何通过子节点找父节点(重要)？ \(c\left[ x \right]\) 的父节点为 \(c\left[ x+\mathrm{lowbit}\left( x \right) \right]\)。常用于树状数组的修改操作(难以理解)，伪代码为：for(int i = x; i <= n; i += lowbit(i)) tree[i] += add; 为什么修改某一个数仅会影响到该数在树状数组对应的一个分叉路径？
查询的伪代码为：for (int i = x; i > 0; i -= lowbit(i)) res += tree[i];