单点更新，区间查询

class Binary_indexed_trees{
private:
    int n;
    vector<int> tree;
public:
    Binary_indexed_trees(int _n):n(_n), tree(_n + 1) {}

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

    void update(int x, int d){
        while(x <= n){
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int sum(int x) const {
        int ans = 0;
        while(x){
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

区间更新，单点查询

单点的值用前缀和表示 即 c[i] = a[1] + a[2] + ... + a[i - 1] + a[i]
区间[x, y]增加k 即a[x] + k, a[y + 1] - k,这样对于x->y的前缀和都加k，y+1前缀和并没变

class BIT{
public:
    int n, m;
    vector<int> c;

    BIT(int _n) : n(_n),  c(_n + 1){
    }
    
    int lowbit(int x){
        return x & (-x);
    }
    //更新单点信息
    void _update(int i, int k){
        while(i <= n){
            c[i] += k;
            i += lowbit(i);
        }
    }
    
    int getSum(int i){
        int res = 0;
        while(i > 0){
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
    //区间[x, y]增加k
    void update(int x, int y, int k){
        _update(x, k);
        _update(y + 1, -k);
    }
};

区间更新，区间查询

class BIT{
private:
    int n;
    vector<int> sum1, sum2;
public:
    BIT(int _n) : n(_n), sum1(_n + 1, 0), sum2(_n + 2, 0){}

    static constexpr lowbit(int x){
        return x & (-x);
    }
    //更新单点
    void _update(int x, int k){
        int i = x;
        while(x <= n){
            sum1[x] += k;
            sum2[x] += (i - 1) * k;
            x += lowbit(x);
        }
    }
    // 更新区间
    void update(int x, int y, int k){
        _update(x, k);
        _update(y + 1, -k);
    }
    // 求单点的值
    int _getSum(int x){
        int res = 0, i = x;
        while(x > 0){
            res += i * sum1[i] - sum2[i];
            i -= lowbit(x);
        }
        return res;
    }
    // 求区间的值
    int getSum(int x, int y){
        return _getSum(y) - _getSum(x - 1);
    }
};

树状数组模板

原文：https://www.cnblogs.com/bgyx-hyyy/p/14060030.html