• 树状数组

struct FenwickTree{
    std::vector<ll>tr;
    int n; 
    FenwickTree(int si):n(si),tr(si+1,0){};
    void update(int x,ll k){
        for(;x<=n;x+=x&-x)tr[x]+=k;
    }
    ll query(int x){
        ll res=0;
        for(;x;x-=x&-x)res+=tr[x];
        return res;
    }
    ll range(int a,int b){
        return query(b)-query(a-1);
    }
}