树状数组

树状数组和线段树一样，也是用来维护区间信息的，不过实现起来比线段树更加简洁，但是没有线段树灵活、强大。树状数组，很明显就是说数组的逻辑结构是树形的，但是这个树形数组和之前提到过的结构都不太一样，它的子节点和父节点的位置并不是2n，2n+1，2n+2等这种关系，而是通过一个特殊的函数lowbit来获取，lowbit函数实际功能是取当前数字二进制形式从右往左直到遇到1为止所表示的值，比如说十进制6，它的二进制表示为110，lowbit要取的值就是10，也就是2。它可以通过以下方式实现

public int lowBit(int val) {
    return val & -val;
}

并且在查询、和更新树状数组时，使用方式还不一样，在更新时，通过parent = child + lowbit(child) 来获取父节点的位置，而在查询时，通过parent = child - lowbit(child)来获取父节点位置。

下面以数组arr=[1, 2, 3, 4, 5, 6, 7, 8]求区间和为例，看看具体这个树状数组是什么样的。

树状数组实现起来比较简单，主要是理解更新和查询时树的结构。

一般来说，能用树状数组来实现，就用树状数组来实现，因为树状数组实现简单，而且效率要比线段树高一些。