# 面试题51

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

```
示例 1:

输入: [7,5,6,4]
输出: 5
```

## 限制：

* 0 <= 数组长度 <= 50000

## Solutions

1. **merge sort O(nlog(n))**

```cpp
class Solution {
public:
    int res = 0;
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp = vector<int>(nums.size() / 2 + 1);
        merge_sort(nums, 0, nums.size());
        return res;
    }
    void merge(vector<int> & nums, int lo, int mid, int hi) {
        copy(nums.begin() + lo, nums.begin() + mid, tmp.begin());
        int w = lo, i = 0, j = mid, maxi = mid - lo;
        while (i < maxi && j < hi) {
            if (nums[j] < tmp[i]) {
                res += maxi - i;
                nums[w++] = nums[j++];
            }
            else
                nums[w++] = tmp[i++];
        }
        while (i < maxi)
            nums[w++] = tmp[i++];
    }
    void merge_sort(vector<int> & nums, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = lo + ((hi - lo) >> 1);
        merge_sort(nums, lo, mid);
        merge_sort(nums, mid, hi);
        if (nums[mid - 1] > nums[mid])
            merge(nums, lo, mid, hi);
    }
};
```

Or a concise version

1. **fenwick tree O(nlog(n) + nlog(n))**
2. Denotes the position of an element in sorted array as `rank`.
3. Put the fenwick tree aside, the main idea behind this method is quite simple. For each element in array, the number of reversed pairs with this element as the smaller one equals to the number of elements with `higer-rank` `rightward`. Thus the answer of this problem can be calcualted by summing up counts of all numbers.
   * More specifically, Starting from an empty array(all values are set to 0), from back to front of the original aarry, we insert each element into this new array with it's proper position(True rank), then count the number of values inserted `leftwards` before.
   * This step cost `O(n)` time for each element, however, we can reduce it to `log(n)` by using fenwick tree.
4. Fenwick tree is a data structure can be used to efficiently query `prefixsum` of an array.
   * Insertion of an element is represented by increasing value by `1`. Thus counting the number of values inserted equals to summing all values ahead.

```cpp
// Fenwick Tree template
struct FenwickTree {
    vector<int> sums;
    FenwickTree(int n) : sums(n + 1) {}
    void update(int i, int delta) {
        while (i < sums.size()) {
            sums[i] += delta;
            i += lowbit(i);
        }
    }

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

        return sum;
    }

    inline int lowbit(int x){
        return x & (-x);
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        set<int> s(nums.begin(), nums.end());
        unordered_map<int, int> m;

        int rank = 1;
        while (!s.empty()) {
            m[*s.begin()] = rank++;
            s.erase(s.begin());
        }

        int numpair = 0;
        FenwickTree ft(rank - 1);
        // from back to front
        for (int i = nums.size() - 1; i >= 0; i--) {
            rank = m[nums[i]];
            ft.update(rank, 1);
            // number of elements with lower rank rightwards in the original array
            numpair += ft.query(rank - 1);
        }

        return numpair;
    }
};
```

or

```cpp
struct FenwickTree {
    vector<int> sums;
    FenwickTree(int n) : sums(n + 1) {}
    void update(int n, int delta) {
        while (n < sums.size()) {
            sums[n] += delta;
            n += lowbit(n);
        }
    }
    int query(int n) {
        int sum = 0;
        while (n > 0) {
            sum += sums[n];
            n -= lowbit(n);
        }
        return sum;
    }
    inline int lowbit(int n) {
        return n & -n;
    }
};
class Solution {
public:
    inline int index(vector<int> & nums, int n) {
        return lower_bound(nums.begin(), nums.end(), n) - nums.begin();
    }
    int reversePairs(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());


        int res = 0, cnt = sorted.size();
        FenwickTree ft(cnt);
        for (auto n : nums) {
            int pos = index(sorted, n) + 1;
            res += ft.query(cnt) - ft.query(pos);
            ft.update(pos, 1);
        }

        return res;
    }
};
```


---

# 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://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-51.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.