树状数组入门指南（用Python轻松掌握高效前缀和操作）

树状数组的核心思想

树状数组利用了二进制表示的特性。每个位置 i 负责维护一段区间和，这段区间的长度由 i 的二进制最低位的 1 决定。

例如，数字 6 的二进制是 110，最低位的 1 在第 2 位（从右往左数，从 1 开始），所以 6 负责维护长度为 2^1 = 2 的区间。

为了快速找到最低位的 1，我们使用一个神奇的操作：i & -i。这在 Python 中可以直接使用。

Python 实现树状数组

下面是一个完整的树状数组类实现：

class FenwickTree:    def __init__(self, size):        """        初始化树状数组        :param size: 数组大小（通常从1开始索引）        """        self.n = size        self.tree = [0] * (self.n + 1)  # 索引从1开始，所以多分配一个位置    def update(self, index, delta):        """        更新操作：将index位置的值增加delta        :param index: 要更新的位置（从1开始）        :param delta: 增加的值        """        while index <= self.n:            self.tree[index] += delta            index += index & -index  # 移动到父节点    def query(self, index):        """        查询前缀和：从1到index的和        :param index: 查询的结束位置（从1开始）        :return: 前缀和        """        s = 0        while index > 0:            s += self.tree[index]            index -= index & -index  # 移动到前一个区间        return s    def range_query(self, left, right):        """        查询区间[left, right]的和        :param left: 左边界（从1开始）        :param right: 右边界（从1开始）        :return: 区间和        """        return self.query(right) - self.query(left - 1)

如何使用这个树状数组？

让我们通过一个简单例子来演示：

# 创建一个大小为5的树状数组ft = FenwickTree(5)# 初始数组假设为 [0, 0, 0, 0, 0]# 现在我们要把第3个位置设为10ft.update(3, 10)# 把第1个位置设为5ft.update(1, 5)# 查询前3个元素的和print(ft.query(3))  # 输出: 15# 查询区间[2, 4]的和print(ft.range_query(2, 4))  # 输出: 10（因为只有第3位有值）

为什么树状数组如此高效？

关键在于 index & -index 这个位运算操作。它能快速找到当前索引对应的区间长度，从而在 O(log n) 时间内完成更新或查询。

例如，当 index = 6（二进制 110）时：

• -index 在补码中是 ...1111111111010
• index & -index = 110 & 010 = 010 = 2

这正好是 6 的最低位 1 所代表的数值。

应用场景

树状数组在以下场景中非常有用：

• 动态求前缀和或区间和
• 逆序对计数问题
• 离散化后的坐标压缩问题
• 某些需要高效更新和查询的统计问题

总结

通过本教程，你应该已经掌握了树状数组的基本概念和Python实现方法。这种数据结构虽然名字听起来有点吓人，但其实原理并不复杂，关键是理解其基于二进制的区间划分方式。

记住，树状数组最适合处理需要频繁进行单点更新和前缀和查询的问题。在实际编程竞赛或工程开发中，它往往是解决这类问题的首选工具之一。

现在，你可以尝试自己实现一个树状数组，或者将其应用到实际问题中去！