纯纯蒟蒻看不懂各位大佬的题解，搜集了各路大佬的思考方式，做出一些小总结，关于整个思考过程，怎么想到离散化，怎么想到树状数组的过程，而不只是给出解法，大佬轻喷，文章仅供和我一样不太理解的萌新们找找感觉，因为详细所以十分啰嗦，才能保证看得懂，请见谅。
题目原意：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对，求长度为n的序列的逆序对数总数。（n在50W以内，时间复杂度必须在 nlogn 内）
这里不做线段树解法和归并排序的解法（大佬们都讲的很清楚了）仅考虑树状数组
思考点1：暴力枚举要n*n：枚举每一个数，再枚举他前面比他大的数，时间超限，不做考虑
思考点2：从暴力中思考，利用空间换的方法时间，那尝试开一个数组
这个数组要怎么用它比较好，先试着挪用暴力枚举的思想，稍微做点变化：
每次枚举到一个数，就在数组中这个数以及这个数之前的所有数的位置+1，这样下次枚举数字时，如果这个数字比上一个数字小，那上一个数字一定在这个数字的地方标记过。
例如：序列 9 7 3 5 6 ，先开个大一点的数组（假设十个单位大小）初始化全部为0
枚举第一个数时，看一下数组对应位置，为0，那第一个数的逆序对数就是0，然后把1~9的位置全部加一，得到 1 1 1 1 1 1 1 1 1 0 。接下来是第二个数 7 ，看看数组中7的位置，为1，那第二个数的逆序对数就是1，然后把1~7的值再加一，得到 2 2 2 2 2 2 2 1 1 0 ，以此类推，最后累计就行。
为什么可以这么做：这是暴力枚举的数组化体现，实际上我们枚举每个数都在为后面的数做准备，这个时候再看看上面红字就很好理解了。
思考点3：上述方法存在很大缺陷，现在对他进行优化处理：首先是数组大小问题，数组大小至少要比最大那个值还要大，但是n最大为50W，数字却可以无穷无尽的大，考虑压缩。不难发现数据考察的都是相对关系，所以自然就会想到离散化，将所有的数最多压在50W的范围内，稍微做一下映射就行了。
思考点4：数组空间解决了，时间还没压缩，在前面的方法中，每次枚举为n，修改前面的数组也是n，时间复杂度达到n*n，细心的已经发现了，实际上对前面数组的修改都是一整个区间，而且每次获取答案都只查询一个点，这不就是单点查询，区间修改吗，妥妥的树状数组。（单点查询加区间修改的部分大佬们都讲得很清楚了，不再赘述）
这是思考这个题的一个比较顺的想法，但是在写的时候还有另外一种思路。接下来这个方法比较玄乎，思路有跳跃（而且我也太懂怎么来的）但是也有学习的地方（大量废话警告）
先给出样例：9 7 3 5 6 ，上一次使用离散化，这次用离散化的本质：映射
首先对上述映射得到：1 2 3 4 5 ，对上述序列升序排序：得到3 5 6 7 9，由于带着映射一起排序，我们会得到映射数组：3 4 5 2 1。观察一下，原数组的逆序数量恰好等于映射数组的逆序数量。怎么解释 ？ 对于任意一个序列，设逆序数为 x ，初始映射数组逆序数为0（定义出来的，因为是 1 2 3 4 . . . . . n ）如果是冒泡排序来使给定序列升序排序，每次交换都是前后交换，x-1，而由于映射数组也要跟着交换，会让映射数组值逆序值增大，0+1，下一次交换就是x-1-1，0+1+1，这样最后得出结果就是x全部给到了0，所以逆序值是一样的。
下面这一段想跳过可以看红字
但是这样操作起来不是很方便，我们尝试让序列降序排序，这个时候求映射数组的逆序值就已经变成求顺序值了，因为整个操作都是相反的。还是上面整个例子。降序排序之后就是 9 7 6 5 3，映射数组就是 1 2 5 4 3，这个时候是把原序列后面比较大的值往前面提，映射数组的逆序值不断增加，比如说在最后面的6往前提两位到第三个位置，对应映射数组中的5也会往前提两位，变到第三个位置，这个时候原序列的逆序值增加的数目就会和映射数组的逆序值增加数相等，而逆序值增加就是顺序值减少。整个操作做完，原数组逆序值x经过y次操作达到最大x+y，映射数组的顺序值x+y经过y次操作减到x（完全顺序的顺序数和完全逆序的逆序数都是最大值，肯定相等），所以原数组逆序值就和映射数组排序后的顺序值相等。
接下来操作就是遍历新的映射数组，每次的找到的值都去看他在树状数组中的前缀和（树状数组前缀和用lowbit操作，不再赘述，篇幅太长啦），统计进入总计值。然后把树状数组中他和他的父节点的位置都+1，以此类推就是答案。
看不懂？我也是。先看看为什么可以怎么做？首先我们按照降序排序，还是那个例子，排序后原数组9 7 6 5 3，映射数组 1 2 5 4 3 。在处理的时候，拿出1，在一号位置标记，同时他属于父节点2和4（lowbit得出来的），都+1，第二次拿出2，刚才2已经登记过了，这个时候2的位置是1，加入答案，然后把2和父节点4（lowbit得出来的）也都+1 。这样的操作就是在维护区间修改，用logn的操作代替原来的时间为n的操作，而且实际上这个过程就是求排序后的顺序值的过程，（前面证明了这个顺序值和答案相等）像第三次拿到5，会先查询5再查询4（lowbit操作），前面比5小的数就登记在这两个位置，（4位置在前面拿出1，2的时候各自加了一次，所以这个位置是2），以此类推。所以这些操作就是不断调用当前数字之前的所有位置统计过的数，得到的值就是在当前值之前比这个值小的数的个数，再用前面证明的，这个顺序值就是原序列的逆序值。
其实这个方法就是利用逆向思维，把后缀和转化为前缀和从而套用树状数组，顺便在这个转化过程中离散化来压缩，个人感觉还是很值的学习的，下面是思路2的代码。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3104.html