493. Reverse Pairs

https://leetcode.com/problems/reverse-pairs/description/

对每个元素统计它前面值为它二倍的元素个数。统计前/后比它大/小个数用BIT，思路和315. Count of Smaller Numbers After Self一样。BIT能在元素可mutable的要求下以O(lgN)时间求presum，树的每个index对应元素值，里头存的是元素值当前的个数。因此只要根据元素值大小对应到BIT的index，然后对任意想查的元素找到对应的index后，就能以O(lgN)算出所有index和index前（比它大/小）的和（总个数）。这道题比315在查index上麻烦了点，从后往前遍历的话，需要找不超过当前元素值1/2的最大值，用二分法，再用值查对应的index。

/*
 * @lc app=leetcode id=493 lang=cpp
 *
 * [493] Reverse Pairs
 *
 * https://leetcode.com/problems/reverse-pairs/description/
 *
 * algorithms
 * Hard (23.52%)
 * Likes:    613
 * Dislikes: 91
 * Total Accepted:    28.5K
 * Total Submissions: 120.1K
 * Testcase Example:  '[1,3,2,3,1]'
 *
 * 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.
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    class BIT {
    public:
        vector<int> sums;
        BIT(const int N): sums(N + 1, 0) {};
        static inline int lowbit(int x) {return x & (-x);}
        void update(int i, int delta) {
            while (i < sums.size()) {
                sums[i] += delta;
                i += lowbit(i);
            }
        }

        int query(int i) const {
            int sum = 0;
            while (i > 0) {
                sum += sums[i];
                i -= lowbit(i);
            }
            return sum;
        }
    };

    int reversePairs(vector<int>& nums) {
        const int N = nums.size();
        vector<int> v(nums);
        sort(v.begin(), v.end());
        unordered_map<int, int> indices;
        for (int i = 0; i < N; ++i) {
            indices[v[i]] = i + 1;
        }
        int res = 0;
        BIT tree(N);
        for (int i = N - 1; i >= 0; --i) {
            res += tree.query(lower_bound(v.begin(), v.end(), nums[i] / 2.0) - v.begin());
            tree.update(indices[nums[i]], 1);
        }
        return res;
    }
};
// @lc code=end