树状数组 (Fenwick Tree) 入门

什么是树状数组？

树状数组（Binary Indexed Tree 或 Fenwick Tree）是一种精巧的数据结构，它可以在对数时间内完成数组的单点更新和前缀和查询。对于需要频繁更新和查询累积和的场景，它比普通数组（查询 O(n)）和前缀和数组（更新 O(n)）更高效。

核心思想

树状数组的核心思想是利用二进制的特性来管理一个“树状”的结构。数组 C 中的每个元素 C[i] 存储了原始数组 A 中一个特定区间的和。这个区间的长度由 i 的二进制表示中最低位的 1（lowbit）决定。

lowbit(i) 的计算方式是 i & -i。

• 查询前缀和 query(x): sum(1...x) 的值可以通过 C[x] + C[x-lowbit(x)] + C[x-lowbit(x)-lowbit(x-lowbit(x))] + ... 来计算，直到索引变为 0。
• 更新单点 update(x, delta): 当 A[x] 增加 delta 时，需要更新所有包含 A[x] 的 C[i]。这可以通过 C[x] += delta, C[x+lowbit(x)] += delta, C[x+lowbit(x)+lowbit(x+lowbit(x))] += delta, ... 来完成，直到索引超出数组范围。

代码实现

#include <vector>

class FenwickTree {
private:
    std::vector<int> tree;
    int size;

    int lowbit(int x) {
        return x & -x;
    }

public:
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    void update(int i, int delta) {
        while (i <= size) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }
};

总结

树状数组以其简洁的代码和高效的性能，在算法竞赛和实际工程中都有广泛的应用。理解其 lowbit 的工作原理是掌握它的关键。