LC 493. Reverse Pairs

link

 Fenwick Tree:

class Solution {
public:
    int n;
    int reversePairs(vector<int>& nums) {
        n=nums.size();
        vector<int> copy=nums;
        sort(copy.begin(),copy.end());
        vector<int> fenwick(n+1);
        int res=0;
        for(int i=n-1;i>=0;i--){
            int idx=binarysearch(copy,nums[i]);
            if(idx>=0){
                res+=query(fenwick,idx);
            }
            int curidx=binarysearch2(copy,nums[i]);
            update(fenwick,curidx);
        }
        return res;
    }
    
    int query(vector<int>& fenwick, int idx){
        idx++;
        int res=0;
        while(idx>=1){
            res+=fenwick[idx];
            idx-=(idx&-idx);
        }
        return res;
    }
    
    void update(vector<int>& fenwick, int idx){
        idx++;
        while(idx<=n){
            fenwick[idx]++;
            idx+=(idx&-idx);
        }
    }
    
    int binarysearch(vector<int>& copy, int val){
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if((long long)2*copy[mid]<val){
                left=mid+1;
            }else right=mid-1;
        }
        return right;
    }
    
    int binarysearch2(vector<int>& copy, int val){
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(copy[mid]>=val) right=mid-1;
            else left=mid+1;
        }
        return left;
    }
};

segment tree:

class Solution {
public:
    int n;
    vector<int> seg;
    int reversePairs(vector<int>& nums) {
        n=nums.size();
        vector<int> copy=nums;
        sort(copy.begin(),copy.end());
        seg=vector<int>(n<<2);
        int res=0;
        for(int i=n-1;i>=0;i--){
            int lastidx=binarysearch(copy,nums[i]);
            if(lastidx>=0){
                res+=query(0,0,n-1,0,lastidx);
            }
            int curidx=binarysearch2(copy,nums[i]);
            update(0,0,n-1,curidx);
        }
        return res;
    }
    
    int query(int idx, int left, int right, int qleft, int qright){
        if(qleft>right || qright<left) return 0;
        if(qleft<=left && qright>=right) return seg[idx];
        int mid=left+(right-left)/2;
        int l=query(idx*2+1,left,mid,qleft,qright);
        int r=query(idx*2+2,mid+1,right,qleft,qright);
        return l+r;
    }
    
    void update(int idx, int left, int right, int targetidx){
        if(left>targetidx || right<targetidx) return;
        if(left==right){
            seg[idx]++;
            return;
        }
        int mid=left+(right-left)/2;
        update(idx*2+1,left,mid,targetidx);
        update(idx*2+2,mid+1,right,targetidx);
        seg[idx]=seg[idx*2+1]+seg[idx*2+2];
    }
    
    int binarysearch(vector<int>& copy, int val){
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if((long long)2*copy[mid]<val){
                left=mid+1;
            }else right=mid-1;
        }
        return right;
    }
    
    int binarysearch2(vector<int>& copy, int val){
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(copy[mid]>=val) right=mid-1;
            else left=mid+1;
        }
        return left;
    }
};