网上看了一些归并排求逆序对的文章，又看了一些树状数组的，觉得自己也写一篇试试看吧，然后本文大体也就讲个思路（没有例题），但是还是会有个程序框架的 好了下面是正文

–

温馨提示：阅读这段内容需要的知识点：归并排序

— 首先的话，归并排序大家应该都知道的吧？归并排是利用分治的思想，先分后和，分到左右区间相等或相交时在返回上一层进行两个有序小数组交错插入排序，形成一个有序数组，然后层层返回排好序的数组，作为新的小数组插入大数组排序，这就是一个n log n的排序算法（带 log 的算法一般都算是比较快的，只要常数不过大）。然后还是不懂的同学可以百度，这里不细讲了。另外提一提，实在是不会用归并排的话冒泡也是一样可以求逆序对的，累加的话就变成了判断到需要交换时进行，但冒泡的复杂度高了点，是 n^2 了，提交 后会爆几个点就不知道了，得看具体题目和数据。（反正数据一般不会水到让你满分【斜眼笑ing】）

— 其次的话，用归并排求逆序对无非也就是在插入的过程中将 逆序数 ans 累加，然后也没什么不同的了，只要记得归并排模板的话基本也是码的出来的。（个人感觉归并排求逆序队还是挺清晰的，因为这样基本就是套套模板不用想太多）

模板如下，但请别直接复制粘贴，好歹自己打一遍