本文来源于力扣圈子，作者：胡小旭。原文链接：力扣（点击查看）
“树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为 Fenwick 树。其初衷是办理数据压缩里的累积频率（Cumulative Frequency）的打算问题，现多用于高效打算数列的前缀和， 区间和。它可以以 O(logn) 的韶光得到任意前缀和，并同时支持在 O(logn) 韶光内支持动态单点值的修正。空间繁芜度 O(n)。”
文章先先容低位运算（lowbit）的基本知识，再提及如何将一个整数划分为 logn 个区间的运算过程，进而延展到如何将线性序列以树行构造进行存取，接着先容高等数据构造——树状数组的两个基本操作——查询前缀和与单点增加，末了先容了树状数组的一个运用——求解逆序对数。
lowbit（低位）运算
lowbit(n) 定义为非负整数 n 在二进制表示下 “最低位的 1 及其后边所有的 0”构成的数值。
比如：n = 10，其二进制表示为
则其低位
公式
如何打算一个整数 n 中二进制表示下所有位是 1 的数值？
比如 n = 10，则其二进制表示下所有位是 1 的数值有：
朴素算法须要列举整数中所有的位，韶光繁芜度为 O(len)，len 为整数 n 的二进制表示下的位数。
为了高效获取二进制表示下所有位是 1 的数值，可以利用 lowbit 运算，得到韶光繁芜度 O(len)，len 为二进制表示下为 1 的位的个数。
比如 n = 10，lowbit(10) = 2；接着令 n = n - lowbit(n) = 10 - 2 = 8，则 lowbit(n) = lowbit(8) = 8；接着令 n = n - lowbit(n) = 8 - 8 = 0，停滞。
为了得到 n 的第几位为 1，可以对 2 和 8 分别取对数，即
由于 C++ math.h 库的 log 函数因此 e 为底的实数运算，并且繁芜度常数较大，以是可以通过预处理，利用哈希表来代替 log 运算。
C++ 实现
树状数组
假设整数 n，其二进制表示形式为：
代表二进制表示下位为 1 的索引下标值，且假设
那么，可以将区间 [1，n] 划分成 log n 个小区间
比如，
那么 [1，7] 区间可以划分成 [1，4] ，[5，6] 和 [7，7]，其区间长度分别为 lowbit(4) = 4，lowbit(6) = 2 和 lowbit(7) = 1。
利用 lowbit 运算打算区间：
C++ 实现
树状数组是基于以上思想的数据构造，基本用场是掩护序列的前缀和。
那么，假设有序列 A = {1,2,3,4,5,6,7,8}，现在的问题便是如何将这个序列划分成 log n 个小区间。不妨，利用序列的索引值（以 1 为出发点开始计数），根据上述打算区间的办法，将其以如下树形构造展开。
树状数组（Binary Indexed Tree） 以树形构造展开的序列 A
此时，以树形构造展开的序列 A 中的每一个节点都对应着树状数组中的一个值。那么这个值为以当前节点为根的子树中所有节点值的总和。
接着，我们看下以树形构造展开的树状数组是什么样的。
以树形构造展开的树状数组（Binary Indexed Tree）
Index 代表序列 A 中元素的索引，为了方便，以 1 为出发点计数Original Value 代表序列 A 中的元素值BIT Value（Binary Indexed Tree Value)代表树状数组中的值Binary bit 代表索引值的二进制形式Low bit 代表索引值的二进制形式下的地位上图中最大的差异是某些节点中的值发生了变革。这是由于，在以树形构造展开的树状数组中的每一个值代表的是一个区间的总和。这个区间即为我们上述求解的区间，比如一个整数 7，可以将其划分成 [1，4] ，[5，6] 和 [7，7] 三个小区间。那么，这三个小区间的右端值作为索引对应的树状数组中的值即为当前区间元素的总和。
比如 Index = 4 对应的树状数组的值为（BIT Value）10，它代表 [1，4] 这个区间的和。
比如 Index = 6 对应的树状数组的值为 11，它代表 [5，6] 这个区间的和。
基本操作
树状数组支持两个基本操作——查询前缀和，单点增加。
查询前缀和
在寻求序列 A 的前 n 项的前缀和时，即是 n 代表的 log n 个区间的总和。
C++ 代码实现
单点增加
不雅观察父子节点的关系，可以推算出，父节点的索引 parent(i)，为其子节点索引值 + 其低位 —— parent(i) = i + lowbit(i)。
C++ 代码实现
关于查询前缀和与单点增加的打算过程，可以不雅观看下面视频展示的动画。
树状数组与逆序对
对付一个序列 A，如果 i < j，并且 A[i] > A[j] ，那么则称 A[i] 与 A[j] 构成逆序对。利用树状数组数据构造可以求解序列 A 中的逆序对个数。
逆序遍历序列利用树状数组的性子，利用 query 操作获取每一个元素的逆序对数将当前元素更新（update）到树状数组中循环迭代上述步骤，直到遍历所有元素C++ 代码实现
在每一次更新（update）树状数组时，以元素的值作为树状数组的索引，更新的值为 +1，代表个数。
在每一次获取（query） 逆序对数时，存在于树状数组中的元素的索引值都比当前元素的大（逆序遍历），那么自然获取到的树状数组的值即为索引值比当前元素的大，且值比当前元素的小的个数。
把稳，上述的求解过程时，如果序列 A 的值范围较大时，那么须要离散化处理。
参考
《算法竞赛进阶指南》维基百科——树状数组本文作者：胡小旭
声明：本文归作者版权所有，如需转载请联系。文中图片和视频为作者“胡小旭”制作，未经许可严禁修正和翻版利用。
