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, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)

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

其中，`lowbit(x)` 函数返回 $x$ 的二进制表示中最低位的 $1$ 所对应的值，即 $x$ 的最后一个 $1$ 所代表的数值。`update(i, delta)` 函数将第 $i$ 个元素加上 $\delta$，`query(i)` 函数返回前 $i$ 个元素的和。