算法之树状数组详解

树状数组

树状数组（Binary Indexed Tree，简称BIT），也被称为Fenwick树，是一种用于处理数组问题的高效数据结构。它特别适合解决涉及区间查询和更新的问题，尤其是当需要频繁地计算数组的前缀和时。树状数组的核心思想是利用二进制表示法(lowbit函数)来快速定位数组中的区间，并在O(log n)时间内完成单点更新和区间查询操作。(树状数组解决的题目，也能用线段树解决（反过来不一定）。但树状数组实现简单，代码短。)

树状数组的基本操作：
更新操作（单点更新）：
对于数组中的第 i 个元素，更新树状数组中所有包含该元素的区间。
查询操作（区间查询）：
查询数组中从第 i 个元素到第 j 个元素的累积和。
基础知识
lowbit(x)计算——lowbit(x) 可以通过位运算来高效计算。对于一个整数 x，x & (-x) 操作的结果就是 x 的二进制表示中最低位的1。这是因为 -x 的二进制表示中，x 的所有位都被取反，然后加1，这样 x 的最低位的1就变成了0，而其他位都是1。因此，x & (-x) 操作实际上就是将 x 与一个只有 x 最低位的1为1，其他位都是0的数进行与操作。

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

单点更新区间查询

public class BinaryIndexedTree {
    private int[] tree;
    private int size;

    public BinaryIndexedTree(int size) {
        this.size = size;
        tree = new int[size + 1];
    }

    // 计算小于等于i的最大2的幂次方
    private int lowbit(int i) {
        return i & (-i);
    }

    // 单点更新，增加tree[i]的值
    public void update(int i, int val) {
        while (i <= size) {
            tree[i] += val;
            i += lowbit(i);
        }
    }

    // 区间查询，计算[1, i]区间的累积和
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    // 区间查询，计算[l, r]区间的累积和
    public int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

单点修改单点查询

区间修改单点查询

public class FenwickTree {
    private int[] tree;
    private int[] values;
    private int size;

    // 构造函数，初始化树状数组和值数组的大小
    public FenwickTree(int size) {
        this.size = size;
        tree = new int[size + 1];
        values = new int[size + 1];
    }

    // 计算小于等于i的最大2的幂次方
    private int lowbit(int i) {
        return i & (-i);
    }

    // 更新树状数组，反映值的变化
    private void updateTree(int i) {
        while (i <= size) {
            tree[i] += values[i];
            i += lowbit(i);
        }
    }

    // 区间修改，对区间[L, R]内每个元素增加val
    public void rangeUpdate(int L, int R, int val) {
        values[L] += val;
        if (R + 1 <= size) {
            values[R + 1] -= val;
        }
        updateTree(L);
        updateTree(R + 1);
    }

    // 单点查询，查询位置i的值
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return values[i] + sum;
    }
}

区间修改区间查询

307. 区域和检索 - 数组可修改

class NumArray {
    private int[] nums;
    private int[] tree;

    public NumArray(int[] nums) {
        int n = nums.length;
        this.nums = new int[n]; // 使 update 中算出的 delta = nums[i]
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        for (int i = index + 1; i < tree.length; i += i & -i) {
            tree[i] += delta;
        }
    }

    private int prefixSum(int i) {
        int s = 0;
        for (; i > 0; i &= i - 1) { // i -= i & -i 的另一种写法
            s += tree[i];
        }
        return s;
    }

    public int sumRange(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }
}