树状数组求逆序对

逆序对，普通方法数O（n^2）n>=10000就超时了，树状数组可以在O(nlogn)时间内做出。

离散化

1、离散化的思路就是排序，然后就可以将十分大的数变小，而指向位置关系没有变，“逆向”求逆序对，其中，第i个数表示第i大的数在哪

2、代码如下

求值

1、先给大家看看代码：

2、为什么是这样写？我们来模拟一下。

3、其实这个树状数组的结点记录的是≤它的数量，其中，大于的=当前总数-小于等于的，下图表示每个结点的“贡献”

4、把这两段结合起来，就是一个完整的代码