二分索引树（BIT），即Binary Indexed Tree或Fenwick Tree，因其更新和查找操作的时间复杂度都为O(logN)，常用于求数组区间和或最值等问题。应用范围和线段树（Segment Tree）重合，但相比于后者实现起来却更加容易。
要理解二分索引树，让我们来思考下面的一个问题：
我们有一个数组 arr[0 。. . n-1]。我们想
- 计算前 i 个元素的总和。
- 修改数组 arr[i] = x 的指定元素的值，其中 0 <= i <= n-1。
简单的解决方案
从0到i-1运行一个循环并计算元素的总和。要更新一个值，只需执行 arr[i] = x。第一个操作需要 O(n) 时间，第二个操作需要 O(1) 时间。另一个简单的解决方案是创建一个额外的数组并将第 i 个元素的总和存储在这个新数组的第 i 个索引处。现在可以在 O(1) 时间内计算给定范围的总和，但现在更新操作需要 O(n) 时间。如果有大量的查询操作但更新操作的数量很少，这很有效。
我们可以在 O(log n) 时间内同时执行查询和更新操作吗？
答案当然是可以的，一种有效的方法是我们之前提到的线段树（Segment Tree），另一种便是我们今天要讨论的BIT（二分搜索树）。
表示
二叉索引树表示为一个数组。设数组为 BITree[]。二叉索引树的每个节点存储输入数组的一些元素的总和。二叉索引树的大小等于输入数组的大小，记为 n。但在实际代码中为了方便我们实现，通常会将数组大小设为n+1
操作
1. 更新（添加）操作（Update）
将BITree[]数组中所有元素初始化为0，我们需要将我们想要求和的原始数组中的元素按顺序一个个的添加到BITree[]中去，之后想要更新原始数组中的某个元素也可以采用相同的方法，把更新的值和其原来的值的差添加到BITree[]即可， 注意更新操作只对BITree[]有影响。
- 首先将要更新或添加的元素在原始数组里的索引设为 id = i + 1，这是因为我们前文说过将BITree[]的大小设为n+1而非n。
While id <= n:
BITree[id] += value，value为更新的值
id = id + （id & -id）
Loop
下图帮助你理解更新操作
更新函数需要确保在其范围内包含 arr[i] 的所有 BITree 节点都被更新。我们通过重复添加与当前索引的最后一个设置位对应的十进制数来循环 BITree 中的此类节点。
2. 求和操作（getSum）
求和操作的更新操作的思想类似，主要区别在于需要引进新的变量sum即最终结果，且id = id + （id & -id）变为id = id - （id & -id），直到id <= 0。
上图提供了 getSum() 的工作示例，我们不难看出
- BITree[0] 是一个虚拟节点。
- BITree[y] 是 BITree[x] 的父节点，当且仅当 y 可以通过从 x 的二进制（01）表示中删除最后一个1位来获得，即 y = x – (x & (-x))。
- 节点 BITree[y] 的子节点 BITree[x] 存储 y(包含) 和 x(不包含) 之间的元素之和：arr[y,…,x)。
二分索引树为什么可行？
这个想法是基于这样一个事实，即所有正整数都可以表示为 2 的幂的总和，即转化为二进制。例如，19 可以表示为 16 + 2 + 1。BITree 的每个节点都存储 n 个元素的总和，其中 n 是2 的幂。例如，在上面的第一个图中（getSum() 的图）中，前 12 个元素的总和可以通过后 4 个元素的总和（从 9 到 12）加上 8 的总和获得元素（从 1 到 8）。数字 n 的二进制表示中设置的位数为 O(Logn)。因此，我们在 getSum() 和 update() 操作中最多遍历 O(Logn) 个节点。构造的时间复杂度为 O(nLogn)，因为n个元素都要执行update()操作。
下面是BIT的两个主要操作，更新操作和求和操作的简单Python实现
def getsum(BITTree,i):
s = 0
i = i+1
while i > 0:
s += BITTree[i]
i -= i & (-i)
return s
def updatebit(BITTree , n , i ,v):
i += 1
while i <= n:
BITTree[i] += v
i += i & (-i)
注意我们可以扩展BIT来用它求区间元素的和，如rangeSum(l, r) = getSum(r) – getSum(l-1).
BIT的应用还有很多，相关的题目我们会在以后进行讨论。
BIT完整代码实现下载链接：
（包含各种语言：C语言、Python、Java、C++等均有示例）
免费资源下载：BIT