用Python实现树状数组

树状数组（Fenwick Tree）是一种常用的数据结构，用于处理动态序列的前缀和问题。它可以在 $O(\log n)$ 时间内完成单点修改和区间查询操作。下面是用 Python 实现树状数组的示例代码：

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

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

    def update(self, i, val):
        while i <= self.n:
            self.tree[i] += val
            i += self.lowbit(i)

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

在上面的代码中，`FenwickTree` 类的构造函数接受一个整数 `n`，表示数据结构中元素的个数。它创建一个长度为 `n+1` 的数组 `tree`，用于存储树状数组的节点值。

`lowbit` 方法用于计算一个整数的二进制表示中最低位的 1 所对应的值。例如，`lowbit(6)` 的返回值为 2，因为 $6=0b110$，最低位的 1 所对应的值是 2。

`update` 方法用于将序列中某个位置的值加上一个指定的数值。它使用一个 `while` 循环遍历树状数组中对应的节点，并将它们的值加上指定的数值。每次循环时，`i` 的值增加 `lowbit(i)`，即遍历树状数组中 `i` 所对应的节点的父节点。

`query` 方法用于计算序列中某个位置的前缀和。它使用一个 `while` 循环遍历树状数组中对应的节点，并将它们的值累加到 `res` 变量中。每次循环时，`i` 的值减去 `lowbit(i)`，即遍历树状数组中 `i` 所对应的节点的前一个节点。

下面是一个示例，演示如何使用树状数组计算序列的前缀和：

# 创建一个长度为 5 的树状数组
tree = FenwickTree(5)

# 在序列中的位置 3 加上 2
tree.update(3, 2)

# 计算序列的前缀和
assert tree.query(1) == 0
assert tree.query(2) == 0
assert tree.query(3) == 2
assert tree.query(4) == 2
assert tree.query(5) == 2

# 在序列中的位置 5 加上 3
tree.update(5, 3)

# 计算序列的前缀和
assert tree.query(1) == 0
assert tree.query(2) == 0
assert tree.query(3) == 2
assert tree.query(4) == 2
assert tree.query(5) == 5