第36课 树状数组（Fenwick Tree）

1. 学习目标

通过本课的学习，你将能够：

• 理解树状数组的核心思想与二进制索引原理
• 掌握树状数组的两种核心操作（单点更新、区间查询）的实现
• 分析树状数组的时间复杂度（O(log n)）与空间复杂度
• 了解树状数组与线段树的区别和适用场景
• 能够运用树状数组解决典型的前缀和相关问题

2. 核心概念

2.1 什么是树状数组？

树状数组（Fenwick Tree 或 Binary Indexed Tree, BIT）是一种用于高效计算前缀和并支持单点更新的数据结构。它比线段树更简洁，常数因子更小，在处理单点更新、区间查询（或区间更新、单点查询）问题时非常高效。

生活比喻：想象你管理一个图书馆的借书记录。每次有人借书（更新），你需要快速查询某一段时间内的总借书量（区间和）。树状数组就像一个高效的索引系统，让你能快速定位和修改相关数据。

2.2 关键思想：lowbit 函数

树状数组的核心是 lowbit(x) 函数，它返回 x 的二进制表示中最低位的1所代表的数值。例如：

• lowbit(6)：6 的二进制为 110，最低位的1是第2位（从右往左），所以返回 2（即二进制 10）
• lowbit(12)：12 的二进制为 1100，最低位的1是第3位，所以返回 4（即二进制 100）

实现非常简单：

def lowbit(x):
    return x & -x

2.3 树状数组的存储结构

树状数组通常用一个数组 tree[] 表示，其下标从 1 开始（重要！）。每个位置 tree[i] 存储的是原数组中某段区间的和，具体区间由 lowbit(i) 决定。

存储规则：

• tree[i] 存储的区间是 [i - lowbit(i) + 1, i]
• 例如，tree[8] 存储的就是原数组的前8个元素之和（因为 lowbit(8) = 8）

3. 代码示例

class FenwickTree:
    def __init__(self, size):
        """初始化树状数组，大小为size+1（下标从1开始）"""
        self.size = size
        self.tree = [0] * (size + 1)  # 索引0不使用
    
    def lowbit(self, x):
        """返回x的二进制中最低位的1所代表的数值"""
        return x & -x
    
    def update(self, index, delta):
        """单点更新：将原数组位置index的值增加delta"""
        # 注意：index必须从1开始
        while index <= self.size:
            self.tree[index] += delta
            index += self.lowbit(index)  # 向上更新所有相关父节点
    
    def query(self, index):
        """查询前缀和：返回原数组[1, index]的和"""
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= self.lowbit(index)  # 向左累加
        return total
    
    def range_query(self, left, right):
        """区间查询：返回[left, right]的和"""
        return self.query(right) - self.query(left - 1)

# 使用示例
if __name__ == "__main__":
    # 原始数组：[1, 3, 5, 7, 9, 11, 13, 15]
    # 注意：实际使用时，原始数组可以省略，直接操作树状数组
    arr = [1, 3, 5, 7, 9, 11, 13, 15]
    n = len(arr)
    
    # 创建树状数组并初始化
    ft = FenwickTree(n)
    
    # 初始化：将原始数组的值更新到树状数组
    for i in range(n):
        ft.update(i + 1, arr[i])  # 索引从1开始，所以i+1
    
    # 测试查询
    print("前5个元素的和:", ft.query(5))  # 1+3+5+7+9 = 25
    print("第3到6个元素的和:", ft.range_query(3, 6))  # 5+7+9+11 = 32
    
    # 测试更新：将第4个元素增加2
    ft.update(4, 2)  # 原数组位置4的值从7变为9
    print("更新后前5个元素的和:", ft.query(5))  # 1+3+5+9+9 = 27

4. 实践练习

练习1：基础操作（简单）

要求：给定一个初始为空的树状数组（大小为10），执行以下操作：

1. 更新位置3，值增加5
2. 更新位置5，值增加8
3. 查询前4个元素的和
4. 查询位置3到位置5的和

预期输出：

操作后前4个元素的和: 5
操作后第3到5个元素的和: 13

练习2：统计频率（中等）

要求：使用树状数组统计数组中每个数字出现的次数。实现一个 FrequencyCounter 类：

• add(num): 添加一个数字
• count_less_than(num): 返回小于num的数字出现的总次数

假设数字范围为1到N，N由初始化时给定。

示例：

fc = FrequencyCounter(10)  # 数字范围1-10
fc.add(3)
fc.add(5)
fc.add(3)
fc.add(8)
print(fc.count_less_than(6))  # 应该输出3（两个3和一个5）

练习3：区间更新与单点查询（困难）

要求：树状数组可以通过"差分"技巧实现区间更新、单点查询。给定一个长度为n的数组，实现：

• range_update(left, right, delta): 将区间[left, right]的所有元素增加delta
• point_query(index): 查询位置index的当前值

提示：使用差分数组 d[i] = a[i] - a[i-1]，然后对差分数组维护树状数组。

5. 常见错误

1. 索引从0开始：树状数组通常实现为从1开始。如果使用从0开始的数组，会导致逻辑混乱和错误结果。

2. 更新时陷入无限循环：

   # 错误示例：while index <= size 会永远循环，如果size为0
   while index <= self.size:
       self.tree[index] += delta
       index += self.lowbit(index)  # 如果lowbit为0，会导致无限循环
   

   复制+ 追加到编辑器

3. 忘记初始化：如果原始数组不为空，需要逐个元素调用 update 进行初始化，而不是直接赋值。

4. 区间查询公式错误：

   • 正确：query(right) - query(left - 1)
   • 错误：query(right) - query(left)

5. 混淆"单点更新、区间查询"与"区间更新、单点查询"：树状数组可以支持两者，但实现方式不同，需要明确问题类型。

6. 小结

关键要点回顾：

1. 树状数组本质：基于二进制索引的前缀和数据结构
2. 核心操作：
   • update(i, delta): 单点更新，时间复杂度 O(log n)
   • query(i): 前缀和查询，时间复杂度 O(log n)
   • range_query(l, r): 区间查询，通过两次前缀和计算
3. 时间复杂度：初始化 O(n log n)，单次操作 O(log n)
4. 空间复杂度：O(n)
5. 与线段树对比：
   • 树状数组代码更简洁，常数更小
   • 线段树功能更强大（支持区间更新、区间查询等）
   • 选择建议：简单前缀和问题优先用树状数组

适用场景：

• 频繁的单点更新和前缀和查询
• 需要节省空间和代码量的场景
• 离线算法中的预处理（如计算逆序对）
• 动态前缀和问题

扩展思考：

树状数组可以通过"差分"技巧支持区间更新，也可以通过二维扩展支持二维前缀和。理解其二进制本质是掌握各种变体的关键。