树状数组 (Fenwick Tree) 完全入门教程：从前缀和到高级应用

什么是树状数组？

树状数组（Binary Indexed Tree 或 Fenwick Tree）是一种用于高效维护与前缀和处理序列数据的二叉树形数据结构。它支持在 O(log n) 时间复杂度内完成：

• 单点更新：修改数组中某一个元素的值
• 区间查询（前缀和）：快速求出从第 1 个元素到第 i 个元素的总和

在面对频繁的动态修改和查询请求时，树状数组比朴素的前缀和数组更高效（朴素前缀和更新需要 O(n)），且比线段树实现更简洁、常数更小，是算法竞赛与高性能系统中的常客。

适用场景举例：维护排行榜分数即时更新、实时统计用户行为频次、计算逆序对数量、求解区间和问题等。

核心原理：二进制拆分与 lowbit

树状数组的精髓在于将线性数列的下标按二进制表示进行分层管理，每个节点负责一段特定长度的区间和。

lowbit(x) 函数

lowbit(x) 定义为 x 在二进制下最低位的 1 所代表的值。例如：

• x = 6（二进制 110），lowbit(6) = 2（因为二进制 10 是 2）
• x = 12（二进制 1100），lowbit(12) = 4（二进制 100）
• x = 7（二进制 111），lowbit(7) = 1

在计算机中可以用一条位运算得到：

lowbit(x) = x & (-x)

原因在于 -x 在补码表示下是 ~x + 1，按位与之后恰好保留最低位的 1。

树状数组的结构

设原数组为 a[1...n]（下标从 1 开始），树状数组 tree[x] 维护的是以 x 结尾、长度为 lowbit(x) 的区间和：

tree[x] = sum( a[x - lowbit(x) + 1] 到 a[x] )

举例（n=8）：

可以看到这棵树通过区间覆盖实现对任意前缀的快速组合。

基本操作：单点更新与前缀查询

单点更新 (add)

当原数组 a[pos] 增加一个值 delta 时，需要更新所有覆盖了 pos 的树节点。观察树状结构，受影响的下标集合可以由不断往上“跳跃”得到：每次令 pos = pos + lowbit(pos)，直到超出数组长度。

算法过程：

1. while pos <= n：
2. tree[pos] += delta
3. pos = pos + lowbit(pos)

时间复杂度 O(log n)，因为每次跳跃至少使二进制最低位的 1 进位，最多跳跃 log n 次。

前缀和查询 (sum)

求前缀和 S(i) = a[1] + a[2] + ... + a[i] 时，我们需要累加一系列不重叠的区间，这些区间可由下标不断减去 lowbit 得到。

算法过程：

1. result = 0
2. while i > 0：
3. result += tree[i]
4. i = i - lowbit(i)

例如求 S(7)：累加 tree[7]（区间[7,7]）、tree[6]（[5,6]）、tree[4]（[1,4]），正好覆盖 [1,7]。

时间复杂度 O(log n)。

代码实现示例

以下使用 Python 实现带注释的树状数组类（下标 1-based）：

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (size + 1)   # 1-indexed

    # 单点增加：给位置 i 增加 delta (i 从 1 开始)
    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    # 查询前缀和：前 i 个元素的和
    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    # 区间查询：[l, r] 的闭区间和
    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

使用示例：

arr = [0, 3, 1, 4, 1, 5, 9, 2, 6]   # 忽略下标0
ft = FenwickTree(8)
for i in range(1, 9):
    ft.add(i, arr[i])                # 初始化

print(ft.range_sum(2, 5))            # 输出 1+4+1+5 = 11
ft.add(3, 2)                         # 位置3 增加2，原4变6
print(ft.range_sum(2, 5))            # 输出 1+6+1+5 = 13

进阶应用

区间求和与差分

若需要同时支持区间更新（给 [l, r] 每个元素都加 val）和单点查询，可以使用差分思想将更新转变成单点操作。

构造差分数组 d[i] = a[i] - a[i-1]（令 a[0]=0），则：

• 给 a[l..r] 全部加上 val 等价于：d[l] += val 且 d[r+1] -= val
• 查 a[i] 就是求差分数组的前缀和：a[i] = d[1] + ... + d[i]

于是用树状数组维护差分数组，即可在 O(log n) 内完成区间更新和单点查询。代码只需复用上面的 add 和 prefix_sum。

# 区间 [l,r] 增加 val
def range_add(l, r, val):
    ft.add(l, val)
    if r + 1 <= n:
        ft.add(r + 1, -val)

# 单点查询位置 i
def point_query(i):
    return ft.prefix_sum(i)

区间更新与区间查询（双树状数组）

若要同时支持区间增加和区间求和，需使用两个树状数组维护差分及辅助数组。推导如下：

设原数组 a，其差分 d，则前缀和：

S(i) = sum_{j=1}^{i} a[j] = sum_{j=1}^{i} sum_{k=1}^{j} d[k]
     = (i+1) * sum_{k=1}^{i} d[k] - sum_{k=1}^{i} k * d[k]

于是维护 tree1 存 d[k]，tree2 存 k * d[k]。区间更新只需更新 tree1 和 tree2 各自的前缀结尾。查询可计算上述公式。实现略复杂，但仍在 O(log n) 内完成。

二维树状数组简介

二维树状数组可以维护矩阵的子矩阵和并进行单点更新。定义 tree[x][y] 管理区域：

# 单点增加
def add(x, y, delta):
    i = x
    while i <= n:
        j = y
        while j <= m:
            tree[i][j] += delta
            j += j & -j
        i += i & -i

# 子矩阵和：(x1,y1) 到 (x2,y2) 的和
def sum(x, y):
    res = 0
    i = x
    while i > 0:
        j = y
        while j > 0:
            res += tree[i][j]
            j -= j & -j
        i -= i & -i
    return res

def query(x1, y1, x2, y2):
    return sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)

同样能以 O(log n * log m) 解决二维动态区间问题。

复杂度与优缺点分析

* 可以通过线性预处理数组后进行 O(n) 建树：先复制原数组，再从 1 到 n 将 tree[i] 累加到 i+lowbit(i) 上。

优点：

• 代码极短，容易实现且常数小
• 适用于点更新/区间查询、区间更新/点查询，甚至区间更新/区间查询

缺点：

• 不能直接维护最值等复杂区间聚合（虽然可通过一定手段，但不如线段树方便）
• 必须满足可逆运算（前缀和允许做差），对不可减运算难以处理
• 下标必须从 1 开始

实战练习与常见问题

经典题目

1. 逆序对计数：遍历序列，用树状数组维护值域前缀频次，查询比当前数大的元素个数。
2. 区间更新与单点查询（洛谷 P3368）：直接套用差分树状数组。
3. 动态排名：值较小时可维护频率树状数组，插入时 add(val,1)，查询第 k 小使用树状数组上的二分查找。
4. 矩阵区域求和（LibreOJ #133）：二维树状数组模板。

常见误区

• 忘记 1-based 索引：树状所有操作必须下标从 1 开始，若题目给出 0-based 数组需要偏移。
• 更新或查询循环条件错用：更新是 i += lowbit(i)，查询是 i -= lowbit(i)，切勿混淆。
• 区间查询时用错公式：range_sum(l,r) = prefix_sum(r) - prefix_sum(l-1)，注意 l-1。

小技巧

• 树状数组可以实现 O(log n) 求前缀和上界的二分（向后倍增法），用于寻找满足前缀和 ≥ S 的最小下标。
• 许多问题可以用 (位置, 时间) 二维树状数组处理离线带修改的查询。

总结：树状数组是处理动态前缀和的首选工具，其灵巧的二进制设计使得代码量很小却威力巨大。从基础单点更新与查询，到差分技巧实现区间操作，再到二维扩展与二分查找，掌握它将显著提升你解决各类求和与计数问题的效率。

若需获取更多练习与可视化演示，可访问本站“算法可视化”板块进行交互式学习。