树状数组 —— 一种支持单点修改和区间查找的数据结构

树状数组（英语：Binary Indexed Tree）又称为二元索引树，由 Fenwick 于 1994年发明，故又称为 Fenwick 树，其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和、区间和。它支持在 O(logn) 的时间复杂度内得到任意前缀和和区间和，同时支持在 O(logn) 的时间复杂度内动态修改单点的值，空间复杂度为 O(n)。 —— wikipedia

树状数组中的精妙操作 —— lowbit（int x）

借助于位运算的lowbit操作（获取整数二进制表示最低位的1），树状数组得以实现其精妙的功能，其精妙之处请看下文。

// lowbit(x) 返回整数x二进制表示最低位的 1
public int lowbit(int x) {
    return x & (-x);
}

树状数组求前缀和

树状数组底层采用数组存储，数组下标从 1 开始 （不使用 0 号元素），如上图所示是一个长度为16且每个元素均为1的数组构造的树状数组，树状数组中 a[i] 保存着一个原数组的区间和（假设原数组是 nums，下标从 1 开始，区间范围是 nums[i – lowbit(i) + 1 : i] 的闭区间）。

如果我们想计算nums[0 : 7] 的和，我们需要计算 a[7] + a[6] + a[4] :

# 计算数组nums 0 到 7 的和：
a[7] = nums[7:7] 的和, lowbit(7) = 1,下一个索引为 7 - 1 = 6
a[6] = nums[5:6] 的和, lowbit(6) = 2,下一个索引为 6 - 2 = 4
a[4] = nums[1:4] 的和, lwobit(4) = 4,下一个索引为 4 - 4 = 0

求前缀和的代码：

public int sum(int index) {
    if (index <= 0) return 0;
    int sum = 0;
    while (index > 0) {
        sum += arr[index];
        index -= lowbit(index);
    }
    return sum;
}

树状数组求区间和

有了之前求前缀和的基础，求区间和只需要用两个前缀和做差：

public int sum(int l, int r) {
    if (r < l) return 0;
    return sum(r) - sum(l - 1);
}

树状数组的单点更新

树状数组的单点更新可以转化为增量更新，如上图所示，如果我们想要更新 a[3] , 还要更新 a[3]上面的 a[4], a[8] 以及 a[16]。

那么怎么获取需要更新位置的索引呢？不难发现：

index = 3
4 = 3 + lowbit(3)
8 = 4 + lowbit(4)
16 = 8 + lowbit(8)

所以单点更新的代码可以写成这样：

public void update(int index, int v) {
    while (index < arr.length) {
        arr[index] += v;
        index += lowbit(index);
    }
}

如何构造一个树状数组？

树状数组的功能如此强大，前提是能够方便地构造出来。我们可以借助于单点更新的 update 方法来构造树状数组。构造函数传入一个原始数组（下标从 0 开始），设原数组长度为 n，我们创建一个长度为原数组长度 +1 的新数组，然后调用 n 次 update 方法来初始化一个树状数组。

class BIT {
    int[] arr;

    public BIT(int[] nums) {
        int n = nums.length;
        this.arr = new int[n + 1];
        for (int i = 0; i < n; i++) {
            update(i + 1, nums[i]);
        }
    }
    
    ...
}

复杂度对比

故对于求前缀和和区间和的问题，不需要对原数组进行修改时推荐使用前缀和，需要频繁修改原数组时应使用树状数组。

树状数组的应用

以 LeetCode 307 区域和检索 - 数组可修改 为例 ，解题代码如下：

class NumArray {

    BIT bit;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.bit = new BIT(nums);
    }
    
    public void update(int index, int val) {
        int v = val - nums[index];
        nums[index] = val;
        bit.update(index + 1, v);
    }
    
    public int sumRange(int left, int right) {
        return bit.sum(left + 1, right + 1);
    }

    private class BIT {
        int[] arr;

        public BIT(int[] nums) {
            this.arr = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                update(i + 1, nums[i]);
            }
        }

        public int lowbit(int x) {
            return x & (-x);
        }

        public void update(int index, int v) {
            while (index < arr.length) {
                arr[index] += v;
                index += lowbit(index);
            }
        }

        public int sum(int index) {
            if (index <= 0) return 0;
            int sum = 0;
            while (index > 0) {
                sum += arr[index];
                index -= lowbit(index);
            }
            return sum;
        }

        public int sum(int l, int r) {
            if (r < l) return 0;
            return sum(r) - sum(l - 1);
        }
    }

}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

参考资料：
什么是树状数组？让这个12岁的年轻人为你讲解
线段树&树状数组