題目：
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.
leetcode鏈接
Example1:
Input: [1,3,2,3,1]
Output: 2

Example2:
Input: [2,4,3,5,1]
Output: 3

思路：

• 用二叉索引樹(shù)方法（Binary Index Tree）(BIT)，先將數(shù)組復(fù)制一份薯鳍，然后排序蝇摸，這樣做之后我們可以得到具體索引所在位置的元素在整個(gè)數(shù)組中排序的位置媳拴。
• 一邊逆序遍歷原數(shù)組伪嫁，一邊更新索引樹(shù)。因?yàn)槭悄嫘虮闅v亥贸，假如當(dāng)前遍歷到索引為i = k(k <= n -1), 那么索引樹(shù)已經(jīng)有值的元素导饲，一定是出現(xiàn)在k之后。所以如果我們能夠找到小于nums[k]/2的數(shù)谬盐，則可以滿足題目的條件 i < j and nums[i] > 2*nums[j]甸私。

分析第一個(gè)例子：
n = 5, copy = [1, 1, 2, 3, 3]
i=4時(shí)，num = nums[4] = 1飞傀，嘗試在BIT中找小于0.5的數(shù)的索引皇型，得到結(jié)果為0（res = 0）；然后將當(dāng)前的值的索引及其之后的父節(jié)點(diǎn)值加1砸烦。因?yàn)?在copy中首次出現(xiàn)的位置為0弃鸦，也就是為所有元素中第一小的數(shù)，BIT中索引為0+ 1 = 1以及之后的父節(jié)點(diǎn)都增加一幢痘，BIT為[0, 1, 1, 0, 1, 0]唬格。

第一次更新后的BIT

i=3時(shí)，num = nums[3] = 3颜说，嘗試在BIT中找小于1.5的數(shù)的索引购岗，得到索引值為2，在BIT中搜索索引值為2的節(jié)點(diǎn)以及其孩子節(jié)點(diǎn)的的值门粪，得到值為1（res = 1）藕畔；然后將當(dāng)前的值(3)的索引及其之后的父節(jié)點(diǎn)值加1。因?yàn)?在copy中首次出現(xiàn)的位置為3庄拇，BIT中索引為3+1=4以及之后的父節(jié)點(diǎn)都增加一注服，BIT為[0, 1, 1, 0, 2, 0]韭邓。

第二次跟新后的BIT

i=2時(shí)，num = nums[3] = 2溶弟，嘗試在BIT中找小于1.0的數(shù)的索引女淑，得到索引值為0，在BIT中搜索索引值為0的節(jié)點(diǎn)的值辜御，得到值為0（res = 1）鸭你；然后將當(dāng)前的值(2)的索引及其之后的父節(jié)點(diǎn)值加1。因?yàn)?在copy中首次出現(xiàn)的位置為2擒权，BIT中索引為2+1 =3以及之后的父節(jié)點(diǎn)都增加一袱巨，BIT為[0, 1, 1, 1, 3, 0]`。

第三次更新后的BIT

i=1時(shí)碳抄，num = nums[1] = 3愉老，嘗試在BIT中找小于1.5的數(shù)的索引，得到索引值為2剖效，在BIT中搜索索引值為2的節(jié)點(diǎn)以及其孩子節(jié)點(diǎn)的值嫉入，得到值為1（res = 2）；然后將當(dāng)前的值(3)的索引及其之后的父節(jié)點(diǎn)值加1璧尸。因?yàn)?在copy中首次出現(xiàn)的位置為3咒林，BIT中索引為3+1=4以及之后的父節(jié)點(diǎn)都增加一，BIT為[0, 1, 1, 1, 4, 0]爷光。

第四次更新后的BIT

i=0時(shí)垫竞，num = nums[0] = 1，嘗試在BIT中找小于0.5的數(shù)的索引蛀序，得到結(jié)果為0（res = 2）欢瞪；然后將當(dāng)前的值的索引及其之后的父節(jié)點(diǎn)值加1。因?yàn)?在copy中首次出現(xiàn)的位置為0哼拔，也就是為所有元素中第一小的數(shù)引有，BIT中索引為0+ 1 = 1以及之后的父節(jié)點(diǎn)都增加一瓣颅，BIT為[0, 2, 2, 1, 5, 0]倦逐。

第五次更新后的BIT

C++代碼：

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        vector<int> BIT(n+1, 0);
        vector copy = nums;
        sort(copy.begin(), copy.end());
        int res = 0;
        for(int i = n-1; i >= 0; i--){
            int num = nums[i];
            res += search(BIT, index(copy, 1.0*num/2));
            insert(BIT, index(copy, num));
        }
        return res;
    }
    
     void insert(vector<int>& BIT, int i){
         i += 1;
         while(i < BIT.size()){
             BIT[i]++;
             i += (i&-i);
         }
     }
    
    int search(vector<int>& BIT, int i){
        int cnt = 0;
        while(i > 0){
            cnt += BIT[i];
            i -= (i & -i);
        }
        return cnt;
    }
    
   
    
    int index(vector<int>& copy, double val){
        int low = 0, high = copy.size();
        while(low < high){
            int mid = low + (high - low)/2;
            if(copy[mid] >= val) {
                high = mid;
            }
            else{
                low = mid +1;
            }
        }
        return low;
    }
};