# 493. Reverse Pairs

对每个元素统计它前面值为它二倍的元素个数。统计前/后比它大/小个数用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。

```cpp
/*
 * @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


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/315.-count-of-smaller-numbers-after-self/493.-reverse-pairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.