树状数组（Fenwick Tree）

当数组经常修改，同时又需要反复查询区间和时，每次遍历区间会产生重复工作。树状数组通过保存部分区间的和，把单点增加和前缀和查询都降低到 O(log n)。

lowbit 保存了什么？

使用 1 开始的下标，lowbit(i) = i & -i 表示 i 的二进制中最低的有效位对应的值。

tree[i] 保存原数组下标区间 [i - lowbit(i) + 1, i] 的和。例如：

下标 i	lowbit(i)	保存的区间
4	4	[1, 4]
6	2	[5, 6]
7	1	[7, 7]
8	8	[1, 8]

查询前 7 项时，依次访问 7、6、4，把 [7,7]、[5,6]、[1,4] 三段相加。更新第 5 项时，依次更新包含它的节点 5、6、8。

一个完整实现

接口约定：

• add(i, delta)：第 i 项增加 delta，1 ≤ i ≤ n。
• prefix_sum(i)：前 i 项之和，允许 i = 0。
• range_sum(left, right)：查询闭区间 [left, right]。

class FenwickTree:
    def __init__(self, n):
        if n < 0:
            raise ValueError("n must be non-negative")
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        if not 1 <= i <= self.n:
            raise IndexError("update index out of range")
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix_sum(self, i):
        if not 0 <= i <= self.n:
            raise IndexError("prefix index out of range")
        result = 0
        while i > 0:
            result += self.tree[i]
            i -= i & -i
        return result

    def range_sum(self, left, right):
        if not 1 <= left <= right <= self.n:
            raise IndexError("invalid query interval")
        return self.prefix_sum(right) - self.prefix_sum(left - 1)


values = [2, 1, 3, 4, 5]
bit = FenwickTree(len(values))
for i, value in enumerate(values, 1):
    bit.add(i, value)

assert bit.prefix_sum(0) == 0
assert bit.range_sum(2, 4) == 8
bit.add(3, 2)
assert bit.range_sum(2, 4) == 10

按上面的逐项插入方法建树耗时 O(n log n)，空间 O(n)。单次更新和查询都耗时 O(log n)。

“增加”与“赋值”不同

add(3, 2) 表示第三项增加 2，不是变为 2。若需要将当前值 old 改成 new，应执行 add(3, new - old)，并同步保存原数组。

下标 0 不能用于更新

lowbit(0) 等于 0，没有边界校验时，更新循环可能无法前进。本实现会拒绝无效下标。

怎样选择？

数组不变时，前缀和能以 O(1) 查询区间和；动态单点更新配合区间和时，可以考虑树状数组。更一般的区间最值或区间更新需求，可以继续阅读线段树。