跳到主要内容

树状数组

树状数组（Fenwick Tree）是一种高效的数据结构，用于处理动态数组的前缀和查询与单点更新操作。它的时间复杂度为 O(log n)，非常适合处理需要频繁更新和查询的场景。本文将详细介绍树状数组的原理、实现方法以及实际应用。

什么是树状数组？​

树状数组是一种基于二进制索引树（Binary Indexed Tree, BIT）的数据结构，主要用于高效计算数组的前缀和。它能够在 O(log n) 的时间内完成以下两种操作：

  1. 单点更新：更新数组中某个元素的值。
  2. 前缀和查询：计算数组中从第一个元素到某个位置的所有元素的和。

树状数组的核心思想是利用二进制表示的特性，将数组分成多个区间，并通过这些区间的组合来快速计算前缀和。

树状数组的实现​

1. 基本结构​

树状数组的核心是一个数组 tree，其大小通常与原数组相同。每个 tree[i] 存储的是原数组中某个区间的和。具体来说，tree[i] 存储的是原数组中从 i - lowbit(i) + 1 到 i 的元素和，其中 lowbit(i) 是 i 的二进制表示中最低位的 1 所代表的值。

2. 关键操作​

2.1 计算 lowbit​

lowbit(i) 是树状数组中的一个关键函数，用于确定 i 的最低位的 1 所代表的值。它的实现如下：

def lowbit(x):
    return x & -x

2.2 单点更新​

单点更新操作用于更新原数组中某个位置的值，并相应地更新树状数组中的所有相关节点。其实现如下：

def update(tree, index, value):
    while index < len(tree):
        tree[index] += value
        index += lowbit(index)

2.3 前缀和查询​

前缀和查询操作用于计算原数组中从第一个元素到某个位置的所有元素的和。其实现如下：

def query(tree, index):
    res = 0
    while index > 0:
        res += tree[index]
        index -= lowbit(index)
    return res

3. 示例代码​

以下是一个完整的树状数组实现示例：

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

    def lowbit(self, x):
        return x & -x

    def update(self, index, value):
        while index < len(self.tree):
            self.tree[index] += value
            index += self.lowbit(index)

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.lowbit(index)
        return res

# 示例使用
arr = [1, 3, 5, 7, 9, 11]
ft = FenwickTree(len(arr))
for i in range(len(arr)):
    ft.update(i + 1, arr[i])

print(ft.query(3))  # 输出: 9 (1 + 3 + 5)
ft.update(2, 2)     # 将第二个元素从 3 更新为 5
print(ft.query(3))  # 输出: 11 (1 + 5 + 5)

实际应用场景​

树状数组在许多实际问题中都有广泛的应用，以下是一些常见的应用场景：

  1. 动态前缀和查询：在需要频繁更新数组元素并查询前缀和的场景中，树状数组是一个高效的选择。
  2. 逆序对计数：树状数组可以用于高效计算数组中的逆序对数量。
  3. 区间更新与单点查询：通过差分数组的技巧，树状数组也可以用于处理区间更新与单点查询的问题。

总结​

树状数组是一种高效的数据结构，特别适合处理动态数组的前缀和查询与单点更新操作。通过利用二进制表示的特性，树状数组能够在 O(log n) 的时间内完成这些操作。本文介绍了树状数组的基本概念、实现方法以及实际应用场景，希望对你理解和使用树状数组有所帮助。

附加资源与练习​

  • 练习 1：实现一个树状数组，并测试其在动态前缀和查询中的性能。
  • 练习 2：使用树状数组解决逆序对计数问题。
  • 练习 3：探索如何利用树状数组处理区间更新与单点查询的问题。
提示

如果你对树状数组的实现细节还有疑问，可以参考以下资源：