首页 > 编程语言 > 详细

树状数组求逆序对

时间:2019-06-25 16:44:55      阅读:173      评论:0      收藏:0      [点我收藏+]

标签:div   答案   区间   -s   排序   离散化   插入   一个数   pre   

数值统计:任意给定一个集合$a$,如果用$t[val]$保存数值$val$在集合中出现的次数,那么数组$t$在$[l,r]$上的区间和(即$\sum_{i=l}^{r} t[i]$)就表示集合$a$中范围在$[l,r]$内的数有多少个。

    我们可以在集合$a$的数值范围上建立一个树状数组,来维护$t$的前缀和。这样即使在集合$a$中插入或删除一个数,也可以高效的进行统计。

    我们已知逆序对问题可以通过归并排序的方法求解,对于一个序列$a$,若$i < j$且$a[i] > a[j]$,则称$a[i]$与$a[j]$构成逆序对。利用上面数值统计的思路可以得到另一种解法:

  1. 在序列$a$的数值范围上建立树状数组,初始化为全零。
  2. 倒序扫描给定的序列$a$,对于每个数$a[i]$:
    • 在树状数组中查询前缀和$[1,a[i]-1]$,累加到答案$ans$中
    • 执行“单点增加”操作,即把位置$a[i]$上的数加1(相当于$t[a[i]]++$),同时正确维护$t$的前缀和。这表示数值$a[i]$又出现了1次。

核心代码:

 for(int i = n;i >=1;i--)
 {
     ans += sum(a[i] - 1);
     add(a[i], 1);
 }

    在这个算法中,因为是倒序扫描,“已经出现过的数”就是在$a[i]$后边的数,所以我们通过树状数组查询的内容就是“每个$a[i]$后边有多少个比它小”。每次查询的结果之和当然就是逆序对的个数。时间复杂度为$O((N+M)logM)$,$M$为数值范围的大小。

    当数值范围较大时,当然可以先进行离散化,再用树状数组进行计算。不过因为离散化本身就要通过排序来实现,所以在这种情况下就不如直接用归并排序来计算逆序对数了。

树状数组求逆序对

标签:div   答案   区间   -s   排序   离散化   插入   一个数   pre   

原文:https://www.cnblogs.com/lfri/p/11083493.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号