树状数组求逆序对
2020-12-13 03:42
标签：通过 倒序 逆序对 val 表示 数值 strong span 逆序对数 数值统计：任意给定一个集合$a$，如果用$t[val]$保存数值$val$在集合中出现的次数，那么数组$t$在$[l,r]$上的区间和（即$\sum_{i=l}^{r} t[i]$）就表示集合$a$中范围在$[l,r]$内的数有多少个。 我们可以在集合$a$的数值范围上建立一个树状数组，来维护$t$的前缀和。这样即使在集合$a$中插入或删除一个数，也可以高效的进行统计。 我们已知逆序对问题可以通过归并排序的方法求解，对于一个序列$a$，若$i a[j]$，则称$a[i]$与$a[j]$构成逆序对。利用上面数值统计的思路可以得到另一种解法： 核心代码： 在这个算法中，因为是倒序扫描，“已经出现过的数”就是在$a[i]$后边的数，所以我们通过树状数组查询的内容就是“每个$a[i]$后边有多少个比它小”。每次查询的结果之和当然就是逆序对的个数。时间复杂度为$O((N+M)logM)$，$M$为数值范围的大小。 当数值范围较大时，当然可以先进行离散化，再用树状数组进行计算。不过因为离散化本身就要通过排序来实现，所以在这种情况下就不如直接用归并排序来计算逆序对数了。 树状数组求逆序对 标签：通过 倒序 逆序对 val 表示 数值 strong span 逆序对数 原文地址：https://www.cnblogs.com/lfri/p/11083493.html
for(int i = n;i >=1;i--)
{
ans += sum(a[i] - 1);
add(a[i], 1);
}