树状数组

3 分钟阅读 • 329 字 + 457 词
给你一个数组，如何快速地计算任意一段连续子数组的元素和？ 我们可以马上想到使用前缀和。 但是，如果还可以修改数组中的元素呢？ 比如我把下标为 1 的元素修改了，由于所有前缀都包含下标 1，那么就需要更新所有前缀的元素和，更新操作就需要 O(n) 的时间，这太慢了。 能不能把前缀 [1,i] 拆分成若干段连续子数组呢？
如果拆分得太细，比如拆分成 [1,1],[2,2],[3,3],⋯，虽然更新是 O(1) 的，但计算子数组元素和还是得遍历累加，时间复杂度是 O(n)，太慢了。
如何平衡询问和更新的时间复杂度呢？
关键在于如何拆分子数组（区间）。
能否把任意前缀拆分成若干个关键区间，使得更新操作也只会更新若干个关键区间？
这样回答询问时，只需要遍历并累加若干个关键区间的元素和。更新元素时，也只需要遍历并更新若干个关键区间的元素和。
树状数组介绍
tree[i] 存储的是从 i-lowbit(i)+1 到 i 这个区间内所有原始数组元素的和 (数组下标从1开始)
cpp
template<typename T>
class FenwickTree {
    vector<T> tree;

public:
    // 使用下标 1 到 n
    FenwickTree(int n) : tree(n + 1) {}

    // a[i] 增加 val
    // 1 <= i <= n
    void update(int i, T val) {
        for (; i < tree.size(); i += i & -i) {
            tree[i] += val;
        }
    }

    // 求前缀和 a[1] + ... + a[i]
    // 1 <= i <= n
    T pre(int i) const {
        T res = 0;
        for (; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }
};

目录