树状数组的python代码

当然，下面是一个简单的树状数组的 Python 实现代码示例：

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

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

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

    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)


# 使用示例
arr = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]
n = len(arr)
fenwick_tree = FenwickTree(n)

# 构建树状数组
for i in range(1, n + 1):
    fenwick_tree.update(i, arr[i - 1])

# 查询前缀和
print(fenwick_tree.query(5))  # 输出：15

# 查询区间和
print(fenwick_tree.range_query(2, 8))  # 输出：13

# 更新某个位置的值
fenwick_tree.update(3, 2)
print(fenwick_tree.query(5))  # 输出：17

这段代码实现了一个基本的树状数组类 `FenwickTree`，其中 `update` 方法用于更新某个位置的值，`query` 方法用于查询某个位置的前缀和，`range_query` 方法用于查询某个区间的和。你可以根据自己的需求进行修改和扩展。