参考学习资源

• 【电子科技大学】树状数组与ST表

点击查看【bilibili】

• LeetCode315题解

  正文

  基本介绍

  树状数组是用来解决动态前缀和的数据结构。

构造树状数组

由于树状数组的底层是数组，所以需要先构造一个数组的结构。树状数组主要有两个操作：update和query。
update操作表示向树状数组中更新一个元素
query操作表示向树状数组中查询

lowbit操作 => 找到右边第一个1

x & (-x) 或者 x & (~x + 1)

应用场景

• 区间和：[5,8] = sum(8) - sum(4)
• 单点查询：对区间[3,6]中的元素都加上5
  • 由于是求前缀和，所以相当于3到6的时候加上5的影响，6之后去除5的影响即可。（没懂，遇到例题再看吧）

代码实现：

/**
 * 树状数组实现
 */
public class BinaryIndexTree {
    private final int length;  // 树状数组的长度
    private final int[] data;  // 树状数组底层存储（从第1位开始存储）
    public BinaryIndexTree(int length) {
        this.length = length;
        this.data = new int[length + 1];
    }
    /**
     * lowbit操作实现，也可以写成 x & (~x + 1)
     *
     * @param x
     * @return
     */
    public int lowbit(int x) {
        return x & (-x);
    }
    /**
     * 向树状数组查询i之前的前缀和
     *
     * @param i
     * @return
     */
    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += this.data[i];
            i -= lowbit(i);
        }
        return res;
    }
    /**
     * 更新树状数组第i位的值
     *
     * @param i
     * @param delta
     */
    public void update(int i, int delta) {
        while (i <= this.length) {
            data[i] += delta;
            i += lowbit(i);
        }
    }
}