ZTL — 数据结构 — 树状数组

zimindaada · 2020-09-02 18:03:41 · 个人记录

class TreeArray{
    private:
    int tamx, t[maxn];
    inline int lowbit(int x){return (x&-x);}
    public:
    inline void add(int x, int k){
        while(x <= tamx){
            t[x] += k;
            x += lowbit(x);
        }
    }
    inline int pre_sum(int x){
        int ans = 0;
        while(x){
            ans += t[x];
            x -= lowbit(x);
        }
        return ans;
    }
    inline int query(int l, int r){
        return pre_sum(r) - pre_sum(l-1);
    }
}