算法刷题系列（四十四）：树状数组——维护前缀聚合与单点更新

算法刷题系列（四十四）：树状数组——维护前缀聚合与单点更新

如果数组会不断更新单个位置，同时需要频繁查询前缀和或区间和，直接累加前缀要 O(n)，而树状数组（Fenwick Tree，也称 Binary Indexed Tree）能将更新与查询都降到 O(log n)。

树状数组的关键不是建立一棵显式树，而是利用二进制最低位 lowbit(x) = x & -x，让数组中每个节点负责一段长度为 lowbit(x) 的区间。

从前缀和拆成若干块

内部下标使用 1-based。tree[i] 保存原数组下标区间 [i - lowbit(i) + 1, i] 的和。查询前缀 sum(1..i) 后，令 i -= lowbit(i)，逐块向左跳；更新下标 i 时，令 i += lowbit(i)，访问所有覆盖该位置的节点。

本文对外提供 0-based 索引：

• add(index, delta)：给一个位置加上变化量；
• prefix_sum(end)：查询半开前缀 [0, end)；
• range_sum(left, right)：查询半开区间 [left, right)。

不变量：每个树节点始终等于它负责区间内元素之和。更新沿覆盖路径修改这些块；前缀查询把目标前缀拆成互不重叠的负责区间。

Java 实现

public class Main {
    static class FenwickTree {
        private final long[] tree;
        private final int n;

        FenwickTree(int n) {
            if (n < 0) throw new IllegalArgumentException("negative size");
            this.n = n;
            this.tree = new long[n + 1];
        }
        void add(int index, long delta) {
            if (index < 0 || index >= n) throw new IndexOutOfBoundsException();
            for (int i = index + 1; i <= n; i += i & -i) tree[i] += delta;
        }
        long prefixSum(int end) {
            if (end < 0 || end > n) throw new IndexOutOfBoundsException();
            long sum = 0;
            for (int i = end; i > 0; i -= i & -i) sum += tree[i];
            return sum;
        }
        long rangeSum(int left, int right) {
            if (left < 0 || left > right || right > n) throw new IndexOutOfBoundsException();
            return prefixSum(right) - prefixSum(left);
        }
    }

    public static void main(String[] args) {
        FenwickTree bit = new FenwickTree(5);
        long[] values = {3, 1, 4, 1, 5};
        for (int i = 0; i < values.length; i++) bit.add(i, values[i]);
        System.out.println(bit.rangeSum(1, 4)); // 6
        bit.add(2, 2);                         // values[2] 从 4 变为 6
        System.out.println(bit.prefixSum(3));  // 10
    }
}

Python 实现

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

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

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

    def range_sum(self, left: int, right: int) -> int:
        if not 0 <= left <= right <= self.n:
            raise IndexError("invalid range")
        return self.prefix_sum(right) - self.prefix_sum(left)

bit = FenwickTree(5)
for i, value in enumerate([3, 1, 4, 1, 5]):
    bit.add(i, value)
assert bit.range_sum(1, 4) == 6
bit.add(2, 2)
assert bit.prefix_sum(3) == 10
assert bit.range_sum(5, 5) == 0

复杂度与适用边界

单点更新和前缀查询均为 O(log n)，空间 O(n)。半开区间 [left,right) 用两个前缀相减，因此也为 O(log n)。空数组可以构造，但任何单点更新都会越界，空前缀查询返回 0。

Fenwick Tree 特别适合可逆的前缀聚合，如整数和、异或。最小值等不易通过两个前缀“相减”恢复区间结果的运算，不能直接使用相同接口。区间加、区间和可以用两棵树扩展；若需要复杂的区间赋值或多种聚合，线段树通常更灵活。

常见错误有混淆 0-based 与 1-based、把 prefix_sum(end) 误当成包含 end、更新时忘记加一，以及用“新值”直接更新却未转成与旧值的差。本文的 add 明确接收增量，赋值前应计算 delta = newValue - oldValue。

小结

树状数组把前缀分解成若干由二进制最低位确定的区间块。统一采用半开区间、明确更新传增量，可以降低边界错误，并让单点更新与前缀聚合都保持对数复杂度。