题⽬描述
在数组中的两个数字，如果前⾯⼀个数字⼤于后⾯的数字，则这两个数字组成⼀个逆序对。输⼊⼀个数组，求出这个数组中的逆序对的总数。
输⼊⼀个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
示例 1: 输⼊: [7,5,6,4] 输出: 5 限制：0 <= 数组⻓度 <= 50000
思路及解答
暴⼒破解
⾸先，也就是数组中任意两个数，只要前⾯的数⼤于后⾯的数，就是逆序对。先来⼀次暴⼒破解：遍历任意两个数，只要符合条件，总数就增加1。
时间复杂度：O(n²) - 对于每个元素，都需要与后续所有元素比较
空间复杂度：O(1) - 只使用常数级别额外空间
归并排序法（推荐）
在归并排序的基础上稍微改动即可。以数组[8,6,4,2,7,5,3,1]为例：
我们可以发现，其实在合并的过程中，两个有序的数组，可以直接计算出逆序数组的个数。我们以[8,6,4,2,7,5,3,1]，实际上分为 [8,6,4,2] 和 [7,5,3,1]，逆序的个数为第⼀部分 [8,6,4,2] 中的逆序个数+第⼆部分 [7,5,3,1] 中的逆序个数，还有第三部分是 [8,6,4,2] 中的元素相对 [7,5,3,1] 的逆序个数。
分为两半之后的逆序个数，⼀看就是分治法，递归即可，⽽两部分的相对逆序，我们可以在合并有序数组的时候得出。
合并的时候使⽤双指针， i 指向第⼀个数组的第⼀个元素，j指向第⼆个数组的第⼀个元素。哪⼀个元素⼩，就将该元素写⼊新的数组中，同时指针后移。
如果第⼆个数组中的元素⼩于第⼀个数组中的元素，那么就构成了逆序对，逆序对的个数：如果中间分隔是索引是 mid，那么构成逆序对的个数为 mid-i+1 。
核心原理：当左子数组的当前元素 temp[i]大于右子数组的当前元素 temp[j]时，左子数组中从 i到 mid的所有元素都与 temp[j]构成逆序对，因为左右子数组都是有序的
时间复杂度：O(n log n) - 与归并排序相同
空间复杂度：O(n) - 需要临时数组存储
有⼀个很坑的地⽅：只要涉及到加和的地⽅都有可能溢出，⼀旦溢出就会导致结果出错，数据量⼤，很难调试。所以凡是涉及到加和的地⽅都要 % 1000000007 。
树状数组法
利用树状数组（Fenwick Tree）和离散化技术统计逆序对
间复杂度：O(n log n) - 离散化O(n log n)，树状数组操作O(log n)
空间复杂度：O(n) - 树状数组和映射表空间