ACM 学习篇 10：树状数组（Fenwick Tree）

上一篇讲了二叉搜索树，它能高效支持搜索、插入、删除和有序遍历。但如果问题只需要区间求和和单点修改，BST 就显得太重了。树状数组（Binary Indexed Tree，也叫 Fenwick Tree）就是专门解决这类问题的轻量级数据结构，代码短、常数小、实现简单，是 ACM 中最常用的数据结构之一。

为什么需要树状数组

假设有一个数组，需要频繁做两种操作：

• 单点修改：把某个位置的值加上一个数；
• 区间查询：查询某个区间的和。

如果用普通数组，单点修改是 O(1)，但区间查询是 O(n)；如果用前缀和数组，区间查询是 O(1)，但单点修改会破坏整个前缀和，变成 O(n)。

树状数组把两者结合起来：单点修改 O(log n)，区间查询 O(log n)。而且代码比线段树短得多，常数也更小。

树状数组的核心思想：lowbit

树状数组的关键是利用二进制的性质。定义 lowbit(x) 为 x 的二进制表示中最低位的 1 代表的值：

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

原理：-x 是 x 的补码，相当于把 x 的所有位取反再加 1。这样 x 和 -x 做与运算，只会保留最低位的 1。

举例：

x = 6  = 0110
-x = -6 = 1010（补码）
x & (-x) = 0010 = 2

lowbit 的值决定了每个节点"管辖"的范围。树状数组中，节点 i 管理区间 [i - lowbit(i) + 1, i]。

树状数组的结构

假设原数组是 a[1..n]，树状数组 tree[1..n] 存的是：

tree[i] = a[i - lowbit(i) + 1] + ... + a[i]

比如 n = 8：

tree[1] = a[1]                    （lowbit(1) = 1，管辖 [1, 1]）
tree[2] = a[1] + a[2]              （lowbit(2) = 2，管辖 [1, 2]）
tree[3] = a[3]                     （lowbit(3) = 1，管辖 [3, 3]）
tree[4] = a[1] + a[2] + a[3] + a[4]（lowbit(4) = 4，管辖 [1, 4]）
tree[5] = a[5]                     （lowbit(5) = 1，管辖 [5, 5]）
tree[6] = a[5] + a[6]              （lowbit(6) = 2，管辖 [5, 6]）
tree[7] = a[7]                     （lowbit(7) = 1，管辖 [7, 7]）
tree[8] = a[1] + ... + a[8]        （lowbit(8) = 8，管辖 [1, 8]）

画成树形结构：

        tree[8] (1-8)
       /        \
   tree[4]      tree[6]    tree[7]
   (1-4)        (5-6)      (7)
  /    \        /    \
tree[2] tree[3] tree[5]
(1-2)  (3)      (5)
  |
tree[1]
(1)

单点更新

把 a[i] 加上 delta，需要更新所有"管辖" i 的节点。这些节点是：i, i + lowbit(i), i + lowbit(i) + lowbit(...), ...，直到超出 n。

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

每次 i 加上 lowbit(i)，相当于跳到上一层"更大的管辖节点"。最多跳 log n 次。

前缀查询

查询前缀和 a[1] + a[2] + ... + a[i]，需要累加所有"覆盖"这个范围的节点。这些节点是：i, i - lowbit(i), i - lowbit(i) - lowbit(...), ...，直到 i 变成 0。

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

每次 i 减去 lowbit(i)，相当于去掉当前节点管辖的范围，跳到下一个需要累加的节点。最多跳 log n 次。

区间查询

查询区间 [l, r] 的和，用前缀和相减：

int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

初始化

初始化树状数组，可以先把 tree 清零，然后对每个 a[i] 执行 update：

void init() {
    memset(tree, 0, sizeof(tree));
    for (int i = 1; i <= n; i++) {
        update(i, a[i]);
    }
}

更高效的做法是直接计算每个 tree[i]：

void initFast() {
    for (int i = 1; i <= n; i++) {
        tree[i] = a[i];
        int j = i + lowbit(i);
        if (j <= n) tree[j] += tree[i];
    }
}

完整模板

class FenwickTree {
private:
    vector tree;
    int n;

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

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

典型题：逆序对

逆序对是树状数组最经典的应用。给定数组，统计有多少对 (i, j) 满足 i < j 但 a[i] > a[j]。

思路：从左到右遍历，对每个元素 a[i]，统计之前有多少个比它大的数。用树状数组维护已出现的数的频率，查询时用 query(MAX) - query(a[i]) 得到比 a[i] 大的数量。

long long countInversions(vector& a) {
    int n = a.size();
    // 如果值域太大，需要离散化
    vector b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    FenwickTree ft(b.size());
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        // 离散化：把 a[i] 映射到 1..m
        int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        // 统计之前有多少个比 a[i] 大的
        ans += ft.query(b.size()) - ft.query(idx);
        ft.update(idx, 1);
    }

    return ans;
}

注意：如果值域很大（比如 10^9），需要先离散化，把值映射到 1..m 的范围。

典型题：动态第 K 小

树状数组还可以用来求动态序列的第 K 小元素。思路是给每个值维护出现次数，然后用类似二分的方法找第 K 小。

int findKth(FenwickTree& ft, int k, int maxVal) {
    int pos = 0;
    int bit = 1;
    while (bit <= maxVal) bit <<= 1;
    bit >>= 1;

    while (bit > 0) {
        int next = pos + bit;
        if (next <= maxVal && ft.query(next) < k) {
            pos = next;
            k -= ft.query(next);
        }
        bit >>= 1;
    }
    return pos + 1;
}

树状数组 vs 线段树

特性	树状数组	线段树
单点修改	O(log n)	O(log n)
区间查询	O(log n)	O(log n)
区间修改	需要差分技巧	原生支持
代码长度	短（~20 行）	长（~50 行）
常数	小	较大
空间	O(n)	O(4n)
灵活性	只能处理可合并的信息	可以处理更复杂的操作

简单说：能用树状数组就用树状数组，需要区间修改或更复杂操作时才用线段树。

树状数组的易错点

• 下标从 1 开始：树状数组的下标必须从 1 开始，因为 lowbit(0) = 0，会导致死循环。
• 离散化别忘了：逆序对等题目如果值域很大，必须先离散化。
• 区间修改需要差分：普通树状数组不支持区间修改，但可以用"差分树状数组"实现：维护差分数组，区间修改变成两个单点修改，前缀和变成单点查询。
• long long 防溢出：逆序对数量可能很大，统计时用 long long。
• query(l - 1) 的边界：如果 l = 1，query(0) 会返回 0，没问题。

差分树状数组：支持区间修改

如果需要支持区间修改（把 [l, r] 都加上 delta），可以用差分思想：

• 维护差分数组 d[i] = a[i] - a[i-1]；
• 区间修改 [l, r] 加 delta：只需 d[l] += delta，d[r+1] -= delta；
• 单点查询 a[i]：就是 d[1] + d[2] + ... + d[i]。

用树状数组维护差分数组，就能做到区间修改 O(log n)，单点查询 O(log n)。

class DiffFenwick {
private:
    FenwickTree ft;

public:
    DiffFenwick(int n) : ft(n) {}

    void rangeUpdate(int l, int r, int delta) {
        ft.update(l, delta);
        ft.update(r + 1, -delta);
    }

    int pointQuery(int i) {
        return ft.query(i);
    }
};

什么时候用树状数组

看到这些关键词，优先考虑树状数组：

• 单点修改 + 区间求和（最经典场景）
• 逆序对（统计比当前大/小的数量）
• 动态排名/第 K 小（维护频率，二分找位置）
• 区间修改 + 单点查询（用差分树状数组）
• 需要 O(log n) 但线段树太重

这一篇先记住什么

• lowbit(x) = x & (-x)：树状数组的核心，决定每个节点管辖的范围
• 单点更新：i += lowbit(i)，向上跳
• 前缀查询：i -= lowbit(i)，向下累加
• 区间查询：query(r) - query(l - 1)
• 逆序对：遍历时统计之前比当前大的数量，需要离散化
• 下标从 1 开始，否则 lowbit(0) = 0 会死循环
• 区间修改用差分树状数组：两个单点更新 + 前缀查询

下一篇继续数据结构：线段树。它能支持更复杂的区间操作，比如区间修改、区间最值查询，是树状数组的"升级版"。