树状数组

1. 模板

    int n;
    vector<int> tree;

    int lowbit(int x) {
        return x & -x;
    }
    
    int query(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= lowbit(i))
            ans += tree[i];
        return ans;
    }

    void update(int x, int u) {
        for(int i = x; i <= n; i += lowbit(i))
            tree[i] += u;
    }

2. 初始化

    // BIT从1开始, 需要整体往右偏移
    n = nums.size();
    tree.resize(n + 1, 0);

3. 单点更新 + 区间更新

    // 单点更新
    update(idx + 1, val)

    // 区间更新

4. 单点查询 + 区间查询

    // 单点查询
    ans = query(idx + 1);

    // 区间查询
    // 前缀和 sum[l, r] = presum[r] - presum[l - 1]
    ans = query(right + 1) - query(left);