逆序对

纯树状数组模板题

class Solution {
private:
    const int mod=1000000007;
    int c[200010];
    struct node{
      int val,id;
      friend bool operator<(node &a,node& b){
          return a.val<b.val;
      }
    }t[200010];
public:
    int InversePairs(vector<int> data) {
        int len=data.size();
        int ans=0;
        for(int i=0;i<len;i++){
            t[i].val=data[i];
            t[i].id=i+1;
            c[i+1]=0;
        }
        sort(t,t+len);
        for(int i=0;i<len;i++){
            insert(t[i].id,len);
            ans=(ans+i+1-getsum(t[i].id))%mod;
        }
        return ans;
    }
    int lowbit(int n){
        return n&(-n);
    }
    void insert(int pos,int n){
        while(pos<=n){
            c[pos]++;
            pos+=lowbit(pos);
        }
        return ;
    }
    int getsum(int pos){
        int sum=0;
        while(pos>0){
            sum+=c[pos];
            pos-=lowbit(pos);
        }
        return sum;
    }
};