树状数组 Fenwick Tree：lowbit 与动态前缀和

“树状数组 Fenwick Tree：lowbit 与动态前缀和”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：树状数组的 lowbit 看起来像魔法，我第一次实现时只是照抄 x & -x，不知道它为什么能跳到该维护的区间。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。

树状数组，也叫 Binary Indexed Tree，常用于动态前缀和。它比线段树短很多，常数也小，但能力范围更窄。它最适合单点修改 + 前缀查询。

它从哪里来

Peter Fenwick 在 1994 年发表 Binary Indexed Tree，用紧凑数组维护动态累计频率。它不显式保存完整树结构，而是让下标的最低有效位决定每个位置负责的区间，因此代码短、常数小、特别适合前缀统计。

树状数组的核心

树状数组 lowbit

图：每个 bit[i] 管理一段长度为 lowbit(i) 的区间

树状数组使用 lowbit 找到一个位置负责的区间长度。

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

例如：

i	二进制	lowbit(i)	bit[i] 覆盖
1	001	1	`[1,1]`
2	010	2	`[1,2]`
3	011	1	`[3,3]`
4	100	4	`[1,4]`
8	1000	8	`[1,8]`

单点增加

class Fenwick {
    private final int[] tree;

    Fenwick(int n) {
        tree = new int[n + 1];
    }

    void add(int index, int delta) {
        for (int i = index; i < tree.length; i += i & -i) {
            tree[i] += delta;
        }
    }
}

树状数组通常使用 1-based 下标，能让 lowbit 逻辑更自然。

前缀查询

int prefixSum(int index) {
    int ans = 0;
    for (int i = index; i > 0; i -= i & -i) {
        ans += tree[i];
    }
    return ans;
}

int rangeSum(int left, int right) {
    return prefixSum(right) - prefixSum(left - 1);
}

查询 prefixSum(i) 时，不断减去 lowbit(i)，相当于把前缀拆成几个互不重叠的小区间。

和线段树对比

对比	树状数组	线段树
代码复杂度	低	较高
空间	`O(n)`	常见 `O(4n)`
单点修改	支持	支持
区间查询	支持前缀可差分的类型	更通用
区间修改	可通过差分变形支持部分场景	懒标记更通用

树状数组适合求和、计数这类可以做差的前缀问题；如果要维护区间最大值、复杂区间状态，线段树通常更自然。

典型应用：逆序对

统计逆序对时，可以从右往左扫描，用树状数组统计当前数右边有多少比它小的数。由于值可能很大，需要先离散化。

long countInversions(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    Fenwick bit = new Fenwick(nums.length);
    long ans = 0;
    for (int i = nums.length - 1; i >= 0; i--) {
        int rank = lowerBound(sorted, nums[i]) + 1;
        ans += bit.prefixSum(rank - 1);
        bit.add(rank, 1);
    }
    return ans;
}

我的分析

树状数组是典型的“小而美”结构。它不如线段树万能，但在它能解决的问题里非常舒服。遇到动态前缀和、频次统计、逆序对、排名变化，我会优先想树状数组。

面试题

lowbit(x) 为什么可以写成 x & -x？
树状数组为什么通常使用 1-based 下标？
树状数组和线段树怎么选择？
如何用树状数组统计逆序对？
树状数组能否维护区间最大值？有什么限制？