1994年，新西兰奥克兰大学的 Peter M. Fenwick 在《Software: Practice and Experience》期刊上发表了一篇题为"A new data structure for cumulative frequency tables"的论文。这篇看似平淡无奇的论文，却发明了一个代码量极小却威力巨大的数据结构——树状数组（Binary Indexed Tree，简称 BIT），也被称为 Fenwick Tree。

Fenwick 最初的目标是解决数据压缩中的累积频率计算问题，但他没想到这个结构会成为算法竞赛和面试中的常客。与线段树动辄上百行的实现相比，树状数组的核心代码不超过十行，却能高效解决前缀和、区间查询、逆序对计数等经典问题。

前缀和问题的两难困境

假设有一个长度为 $n$ 的数组，需要频繁执行两种操作：查询区间 $[l, r]$ 的和，以及修改某个位置的值。最直观的方案有两种：

方案一：直接存储原数组。修改操作是 $O(1)$，但查询需要遍历整个区间，时间复杂度 $O(n)$。

方案二：预处理前缀和数组。设 $S[i] = A[0] + A[1] + \cdots + A[i]$，则区间 $[l, r]$ 的和为 $S[r] - S[l-1]$，查询只需 $O(1)$。但每次修改一个元素，需要更新后面所有位置的前缀和，时间复杂度 $O(n)$。

两种方案都是"一头快、一头慢"，无法同时优化两种操作。能不能找到一种折中方案，让两种操作都快起来？树状数组就是这个问题的答案——它将查询和修改的时间复杂度都降到了 $O(\log n)$。

lowbit：树状数组的核心魔法

理解树状数组的关键在于一个看似简单的位运算：lowbit(x) = x & (-x)。这个操作提取的是整数 $x$ 二进制表示中最低位的 1 及其后面的 0 所组成的数。

以 $x = 12$ 为例，其二进制表示为 $(1100)_2$。在计算机中，负数用补码表示，$-12$ 的补码计算过程是：先取反得到 $(0011)_2$，再加一得到 $(0100)_2$。两者按位与的结果是 $(0100)_2 = 4$。这正是 12 的二进制中最低位的 1 所代表的值。

为什么这个操作如此重要？因为它揭示了数字的二进制结构与区间长度之间的美妙关系。在树状数组中，每个位置 $i$ 存储的不是单个元素，而是一个长度为 lowbit(i) 的区间和。

树状数组的索引映射

树状数组使用 1-indexed 索引。设原数组为 $A[1 \ldots n]$，树状数组为 $BIT[1 \ldots n]$，则：

$$BIT[i] = \sum_{j = i - \text{lowbit}(i) + 1}^{i} A[j]$$

也就是说，$BIT[i]$ 存储的是从 $i$ 开始向前数 lowbit(i) 个元素的和。例如：

  • $BIT[1]$：$\text{lowbit}(1) = 1$，存储 $A[1]$
  • $BIT[2]$：$\text{lowbit}(2) = 2$，存储 $A[1] + A[2]$
  • $BIT[3]$：$\text{lowbit}(3) = 1$，存储 $A[3]$
  • $BIT[4]$：$\text{lowbit}(4) = 4$，存储 $A[1] + A[2] + A[3] + A[4]$
  • $BIT[6]$：$\text{lowbit}(6) = 2$，存储 $A[5] + A[6]$
  • $BIT[8]$：$\text{lowbit}(8) = 8$，存储 $A[1] + \cdots + A[8]$
graph TD
    subgraph 树状数组结构
        A8["BIT[8]<br/>A[1..8]"]
        A4["BIT[4]<br/>A[1..4]"]
        A6["BIT[6]<br/>A[5..6]"]
        A7["BIT[7]<br/>A[7]"]
        A2["BIT[2]<br/>A[1..2]"]
        A3["BIT[3]<br/>A[3]"]
        A5["BIT[5]<br/>A[5]"]
        A1["BIT[1]<br/>A[1]"]
        
        A8 --> A4
        A8 --> A6
        A8 --> A7
        A4 --> A2
        A4 --> A3
        A6 --> A5
        A2 --> A1
    end

这种设计的精妙之处在于：任何一个前缀和 $A[1] + \cdots + A[i]$ 都可以分解为若干个不相交的 $BIT$ 元素之和。例如，查询前 13 个元素的和：

$$13 = (1101)_2 = 8 + 4 + 1$$

对应地，$BIT[13] + BIT[12] + BIT[8]$ 恰好覆盖了前 13 个元素。其中：

  • $BIT[13]$ 覆盖 $A[13]$（长度 1）
  • $BIT[12]$ 覆盖 $A[9 \ldots 12]$（长度 4）
  • $BIT[8]$ 覆盖 $A[1 \ldots 8]$（长度 8）

查询操作：不断去掉最低位的 1

前缀和查询的实现非常简洁：从位置 $i$ 开始，累加 $BIT[i]$，然后执行 $i = i - \text{lowbit}(i)$，直到 $i = 0$。

// 查询前缀和 A[1] + ... + A[i]
public int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i)) {
        sum += bit[i];
    }
    return sum;
}

// 查询区间和 A[l] + ... + A[r]
public int queryRange(int l, int r) {
    return query(r) - query(l - 1);
}

为什么这样正确？每次执行 i -= lowbit(i)，实际上是将 $i$ 的二进制中最低位的 1 变成 0。由于 $i$ 最多有 $\log n$ 个 1，所以查询的时间复杂度是 $O(\log n)$。

更新操作：不断加上最低位的 1

单点更新同样简洁：更新 $A[i]$ 时，需要更新所有覆盖到 $i$ 的 $BIT$ 元素。从位置 $i$ 开始，更新 $BIT[i]$，然后执行 $i = i + \text{lowbit}(i)$，直到超出数组范围。

// 单点更新：将 A[i] 增加 delta
public void update(int i, int delta) {
    for (; i <= n; i += i & (-i)) {
        bit[i] += delta;
    }
}

为什么更新是向上走？因为 i + lowbit(i) 总是大于 $i$ 的下一个需要更新的位置。例如，更新 $A[3]$：

  • 首先更新 $BIT[3]$
  • $3 + \text{lowbit}(3) = 3 + 1 = 4$，更新 $BIT[4]$
  • $4 + \text{lowbit}(4) = 4 + 4 = 8$，更新 $BIT[8]$
  • 依此类推…

与线段树的对比

树状数组和线段树都能在 $O(\log n)$ 时间内处理区间问题，但各有特点：

特性 树状数组 线段树
代码量 极简，核心代码约10行 较复杂，通常50-100行
空间复杂度 $O(n)$ $O(4n)$
支持的操作 前缀查询、单点更新 任意区间查询、区间更新
适用运算 满足结合律且有逆元的运算 任何满足结合律的运算
实现难度 低 中等

树状数组的一个限制是：只能处理从 1 开始的前缀查询，不能直接查询任意区间 $[l, r]$ 的和。不过，通过前缀和作差（query(r) - query(l-1)）可以间接实现区间查询。

另一个限制是：树状数组不支持"不可逆"的操作，如求区间最大值。要查询区间最大值，需要将查询含义改为后缀最大值，实现较为复杂。而线段树天然支持这类操作。

进阶技巧一：区间更新与单点查询

如果需要支持"区间增加某个值"和"查询单点值"，可以构造一个差分数组 $D[i] = A[i] - A[i-1]$。原数组 $A[i] = \sum_{j=1}^{i} D[j]$。

对区间 $[l, r]$ 增加 $v$，等价于 $D[l] += v$ 和 $D[r+1] -= v$。这只需要两次单点更新！

查询单点 $A[i]$ 的值，就是查询差分数组的前缀和。

// 区间 [l, r] 增加 val
public void rangeAdd(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}

// 查询单点 A[i] 的值
public int pointQuery(int i) {
    return query(i);
}

进阶技巧二：区间更新与区间查询

要同时支持区间更新和区间查询，需要使用两个树状数组。设差分数组为 $D$，则：

$$\sum_{i=1}^{k} A[i] = \sum_{i=1}^{k} \sum_{j=1}^{i} D[j] = \sum_{i=1}^{k} (k - i + 1) \cdot D[i] = k \cdot \sum_{i=1}^{k} D[i] - \sum_{i=1}^{k} (i-1) \cdot D[i]$$

因此，我们维护两个树状数组：

  • $BIT_1$：维护 $D[i]$
  • $BIT_2$：维护 $(i-1) \cdot D[i]$
public class FenwickTreeRange {
    private long[] bit1, bit2;
    private int n;
    
    public FenwickTreeRange(int n) {
        this.n = n;
        bit1 = new long[n + 1];
        bit2 = new long[n + 1];
    }
    
    private void update(long[] bit, int i, long val) {
        for (; i <= n; i += i & (-i)) {
            bit[i] += val;
        }
    }
    
    private long query(long[] bit, int i) {
        long sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
    
    // 区间 [l, r] 增加 val
    public void rangeAdd(int l, int r, long val) {
        update(bit1, l, val);
        update(bit1, r + 1, -val);
        update(bit2, l, val * (l - 1));
        update(bit2, r + 1, -val * r);
    }
    
    // 查询前缀和
    private long prefixSum(int i) {
        return query(bit1, i) * i - query(bit2, i);
    }
    
    // 查询区间和
    public long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

LeetCode 经典题目详解

307. Range Sum Query - Mutable（区域和检索 - 数组可变）

这是树状数组最直接的应用场景：支持单点修改和区间查询。

class NumArray {
    private int[] bit;
    private int[] nums;
    private int n;
    
    public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = new int[n];
        this.bit = 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 <= n; i += i & (-i)) {
            bit[i] += delta;
        }
    }
    
    private int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
    
    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}

315. Count of Smaller Numbers After Self（计算右侧小于当前元素的个数）

这道题的本质是求逆序对的数量变体。对于每个元素，需要统计它后面有多少个比它小的元素。

核心思路是从右向左遍历，每次将当前元素加入树状数组，查询比它小的元素数量。但由于元素值可能很大或为负数，需要进行离散化：将元素值映射到 $[1, m]$ 的范围内。

class Solution {
    private int[] bit;
    private int n;
    
    public List<Integer> countSmaller(int[] nums) {
        // 离散化
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<>();
        int rank = 1;
        for (int num : sorted) {
            if (!ranks.containsKey(num)) {
                ranks.put(num, rank++);
            }
        }
        
        n = rank;
        bit = new int[n];
        Integer[] result = new Integer[nums.length];
        
        // 从右向左遍历
        for (int i = nums.length - 1; i >= 0; i--) {
            int r = ranks.get(nums[i]);
            // 查询比当前元素小的元素数量
            result[i] = query(r - 1);
            // 将当前元素加入树状数组
            update(r, 1);
        }
        
        return Arrays.asList(result);
    }
    
    private void update(int i, int delta) {
        for (; i < n; i += i & (-i)) {
            bit[i] += delta;
        }
    }
    
    private int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
}

493. Reverse Pairs（翻转对）

这道题统计满足 $i < j$ 且 $nums[i] > 2 \times nums[j]$ 的数对数量。与上一题类似，但从右向左遍历时，需要查询的是比 $2 \times nums[j]$ 大的元素数量。

class Solution {
    private int[] bit;
    private int n;
    
    public int reversePairs(int[] nums) {
        // 离散化：需要同时考虑 nums[i] 和 2 * nums[i]
        Set<Long> set = new HashSet<>();
        for (int num : nums) {
            set.add((long) num);
            set.add((long) num * 2);
        }
        long[] sorted = set.stream().mapToLong(Long::longValue).toArray();
        Arrays.sort(sorted);
        Map<Long, Integer> ranks = new HashMap<>();
        int rank = 1;
        for (long num : sorted) {
            ranks.put(num, rank++);
        }
        
        n = rank;
        bit = new int[n];
        int result = 0;
        
        for (int i = nums.length - 1; i >= 0; i--) {
            // 查询比 nums[i] 大的元素数量
            int r = ranks.get((long) nums[i]);
            result += query(n - 1) - query(r);
            // 将 2 * nums[i] 加入树状数组
            update(ranks.get((long) nums[i] * 2), 1);
        }
        
        return result;
    }
    
    private void update(int i, int delta) {
        for (; i < n; i += i & (-i)) {
            bit[i] += delta;
        }
    }
    
    private int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
}

327. Count of Range Sum（区间和计数）

这道题统计满足 $lower \leq \text{sum}(i, j) \leq upper$ 的区间数量。利用前缀和，区间和可以表示为 $S[j] - S[i-1]$，其中 $S$ 是前缀和数组。

问题转化为：对于每个 $j$，统计有多少个 $i \leq j$ 满足 $lower \leq S[j] - S[i-1] \leq upper$，即 $S[j] - upper \leq S[i-1] \leq S[j] - lower$。

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        // 离散化所有需要查询的值
        Set<Long> set = new HashSet<>();
        for (long p : prefix) {
            set.add(p);
            set.add(p - lower);
            set.add(p - upper);
        }
        long[] sorted = set.stream().mapToLong(Long::longValue).toArray();
        Arrays.sort(sorted);
        Map<Long, Integer> ranks = new HashMap<>();
        int rank = 1;
        for (long num : sorted) {
            ranks.put(num, rank++);
        }
        
        int size = rank;
        int[] bit = new int[size];
        int result = 0;
        
        // 先插入 prefix[0] = 0
        update(bit, ranks.get(0L), 1, size);
        
        for (int i = 1; i <= n; i++) {
            long lo = prefix[i] - upper;
            long hi = prefix[i] - lower;
            // 查询 [lo, hi] 范围内的数量
            int loRank = ranks.get(lo);
            int hiRank = ranks.get(hi);
            result += query(bit, hiRank) - query(bit, loRank - 1);
            // 插入当前前缀和
            update(bit, ranks.get(prefix[i]), 1, size);
        }
        
        return result;
    }
    
    private void update(int[] bit, int i, int delta, int n) {
        for (; i < n; i += i & (-i)) {
            bit[i] += delta;
        }
    }
    
    private int query(int[] bit, int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
}

1649. Create Sorted Array through Instructions（通过指令创建有序数组）

这道题要求按顺序插入元素，每次插入时计算代价：min(比当前小的元素数, 比当前大的元素数)。本质上是对每个元素查询两个前缀和。

class Solution {
    private static final int MOD = 1_000_000_007;
    
    public int createSortedArray(int[] instructions) {
        int maxVal = 0;
        for (int num : instructions) {
            maxVal = Math.max(maxVal, num);
        }
        
        int[] bit = new int[maxVal + 2];
        int result = 0;
        
        for (int i = 0; i < instructions.length; i++) {
            int x = instructions[i];
            // 比当前小的元素数量
            int less = query(bit, x - 1);
            // 比当前大的元素数量 = 已插入的总数 - 不大于当前的元素数量
            int greater = i - query(bit, x);
            result = (result + Math.min(less, greater)) % MOD;
            // 插入当前元素
            update(bit, x, 1, maxVal + 1);
        }
        
        return result;
    }
    
    private void update(int[] bit, int i, int delta, int n) {
        for (; i <= n; i += i & (-i)) {
            bit[i] += delta;
        }
    }
    
    private int query(int[] bit, int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += bit[i];
        }
        return sum;
    }
}

树状数组的其他应用

逆序对计数

逆序对问题是树状数组的经典应用。给定一个排列或数组，统计满足 $i < j$ 且 $A[i] > A[j]$ 的数对数量。

思路是：从左向右遍历，每次将当前元素加入树状数组，查询已经加入的元素中比当前元素大的数量。或者从右向左遍历，查询比当前元素小的数量。

LIS 长度的优化

求最长递增子序列的朴素 DP 是 $O(n^2)$。使用树状数组可以优化到 $O(n \log n)$：对于每个元素，查询比它小的元素中最大的 LIS 长度，然后更新当前位置。

二维树状数组

树状数组可以自然地扩展到二维。设 $BIT[i][j]$ 表示以 $(i, j)$ 为右下角的矩形区域内的和，查询和更新都涉及两层循环，时间复杂度 $O(\log n \cdot \log m)$。

总结

树状数组是一个代码极简却功能强大的数据结构。它的核心思想是利用二进制的性质，将前缀和分解为若干个不相交的区间之和。相比线段树，树状数组的实现更加简洁，常数因子更小，但功能上有所限制——只能处理前缀查询和满足结合律且有逆元的运算。

在 LeetCode 中，树状数组常用于处理以下场景：

  1. 动态前缀和问题：如 LeetCode 307，需要同时支持修改和查询
  2. 逆序对及相关计数问题：如 LeetCode 315、493、1649
  3. 前缀和的区间查询：如 LeetCode 327，利用前缀和转化问题

掌握树状数组，关键在于理解 lowbit 操作的数学意义，以及如何将问题转化为前缀查询的形式。当问题涉及"统计比某元素大/小的元素数量"、“区间和的计数"等场景时，树状数组往往是首选方案。

参考资料

  1. Fenwick, P. M. (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3), 327-336.
  2. CP-Algorithms. Fenwick Tree. https://cp-algorithms.com/data_structures/fenwick.html
  3. LeetCode Discuss. Binary Index Tree Template and Problem Solving. https://leetcode.com/discuss/study-guide/1569634/
  4. Halfrost. 聊聊树状数组 Binary Indexed Tree. https://halfrost.com/binary_indexed_tree/