作用

如果你需要经常修改一个数组中的值，同时又需要计算这个数组的前N项和，此时，你希望计算和的效率高一点的时候，就可以尝试树状数组

关键方法

update(i, v)：更新第i个元素，加上V
sum(n)：查询序列前N个元素的和
lowbit(int i):这个研究他的特征，不如直接打印结果，然后去感受效果更好

我的理解过程

我先把 lowbit(int i)，也就是 i & -i,的结果，for循环全部打印尝试了一遍（代码注释中有）
然后尝试理解update 和 sum的概念，同时DEBUG一遍代码，突然就通了

代码

class BitTree{
    int[] nums = null;
    int length = 0;

    public BitTree(int length){
        nums = new int[length+1];
        this.length = length;
    }

    /**
     * 这个方法非常的神奇，你可以尝试打印他的值，然后发现他的规律吧
     *         for (int i = 1; i < 181; i++) {
     *             System.out.print(lowbit(i) + "  ");
     *             if(i%16 == 0){ // 可以修改这个16，变为 2，4，8，16，32 看看有什么不同
     *                 System.out.println();
     *             }
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  16
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  32
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  16
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  64
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  16
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  32
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  16
     * 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1  128
     * @param i
     * @return
     */
    public int lowbit(int i){
        return i&-i;
    }

    public void update(int i,int v){
        while (i <= length){ // 比如传入的 i = 3，被跟下的nums的下标有  3,4,8,16,32,64,128
            nums[i] = nums[i] + v;
            i = i + lowbit(i);
        }
    }


    public int sum(int n){
        int ret = 0;
        while (n != 0){ //建议自己举个例子，然后一步步Debug，看ret加了那些数据的下标
            ret = ret + nums[n];
            n = n - lowbit(n);
        }
        return ret;
    }

}