algo-aha

Fenwick树（二叉索引树）

Fenwick用于数组经常更新时，前缀和（进而范围和）的快速查询。

算法动画

• https://leetcode.com/problems/range-sum-query-mutable/

class FenwickTree {
    static inline int lowbit(int x) { return x & -x; }
    vector<int> _nums;
    vector<int> _tree; // 使用_tree[1..n]
public:
    FenwickTree(const vector<int> &nums)
        : _nums(nums.size()), _tree(nums.size() + 1) { 
        for (int i = 0; i < _nums.size(); i++) {
            update(i, nums[i]);
        }
    }

    void update(int i, int val) {
        int delta = val - _nums[i];
        _nums[i] = val;
        i++;
        while (i < _tree.size()) {
            _tree[i] += delta;
            i += lowbit(i);
        }
    }

    // 返回_nums[0..i]的和
    int query(int i) const {
        i++;
        int sum = 0;
        while (i) {
            sum += _tree[i];
            i -= lowbit(i);
        }
        return sum;
    }
};