leetcode493. Reverse Pairs（493. 翻转对）/树状数组

题目：leetcode493. Reverse Pairs（493. 翻转对）

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.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

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

Note:

• The length of the given array will not exceed 50,000.
• All the numbers in the input array are in the range of 32-bit integer.

基本思想1：BST（二叉搜索树）超时了

• 将数组构造成二叉搜索树的形式，对于二叉树的每一个节点增加一个计数域，统计大于等于该数的个数
• 遍历整个数组，遍历的过程中做两个工作：
  • 对于当前元素a，查找已构造的树中大于等于2 * a + 1的元素的个数
  • 将当前节点插入到树中，特别注意更新计数域

时间复杂度分析：

• 平均情况下构建二叉树以及在二叉树中查找结点的时间复杂度为O（logn）
• 但是在二叉树向一段倾斜时，例如单支树，也就是数组降序或者升序的情况下，时间复杂度为O(n)，这样就使得整个算法的时间复杂度达到O（n²），对于该题的数据量而言肯定超时了，这也是为什么一开始没有尝试暴力算法

struct Node{
    Node *left, *right;
    int val;
    int cnt;
    Node(int n){
        left = NULL;
        right = NULL;
        val = n;
        cnt = 1;
    }
};
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int res = 0;
        Node* root = NULL;
        for(int i = 0; i < nums.size(); ++i){
            res += search(root, 2LL * nums[i] + 1); //2LL表示 2 是long long型，这样处理是为了防止当nums[i] * 2 + 1时溢出
            root = insert(root, nums[i]);
        }
        return res;
    }
    //TODO:在树中插入节点
    Node* insert(Node *root, int val){
        if(!root){
            root = new Node(val);
            return root;
        }
        if(val < root->val){
            root->left = insert(root->left, val);
        }
        else if(val == root->val){
            root->cnt++;
        }
        else if(val > root->val){
            root->cnt++;
            root->right = insert(root->right, val);            
        }
        return root;
    }
    //TODO:查找已经构建好的树中大于等于val值的个数
    int search(Node* root, long long val){
        if(!root){
            return 0;
        }
        
        if(root->val == val){
            return root->cnt;
        }
        else if(val < root->val){
            return root->cnt + search(root->left, val);
        }
        else if(val > root->val){
            return search(root->right, val);
        }
        return 0;
    }
};

基本思想2：BIT（Binary Indexed Tree）树状数组

树状数组：用数组来模拟树的结构，而没必要建树
这里要充分理解树状数组的思想，题目中涉及到树状数组的查找和更新

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> nums_copy(nums);
        
        sort(nums_copy.begin(), nums_copy.end());
        
        vector<int> BITS(n + 1, 0);
        int count = 0;
        for(int i = 0; i < n; ++i){
            count += query(BITS, lower_bound(nums_copy.begin(), nums_copy.end(), 2LL * nums[i] + 1) - nums_copy.begin() + 1);
            update(BITS, lower_bound(nums_copy.begin(), nums_copy.end(), nums[i]) - nums_copy.begin() + 1, 1);
        }
        return count;
    }
    int query(vector<int>& BIT, int index){
        int sum = 0;
        while(index < BIT.size()){
            sum += BIT[index];
            index += index & (-index);
        }
        return sum;
    }
    void update(vector<int>& BIT, int index, int val){
        while(index > 0){
            BIT[index] += val;
            index -= index & (-index);
        }
    }
};