树状数组求逆序对个数（AcWing788.逆序对的数量（Java））

题目来源：https://www.acwing.com/problem/content/790/

题目描述

给定一个长度为 n 的整数数列   
    
    
    
    
，请你计算数列中的逆序对的数量    
    
    
    
 。

逆序对的定义如下：对于数列的第 i 个和第 j个元素


     


     


     


     


 ，如果满足 i<j且 a[i]>a[j] 




 




 




 




 ，则其为一个逆序对；否则不是    


     


     


     


     。

输入格式

第一行包含整数 n   

   

   

   

   

，表示数列的长度




 




 




 




 




。

第二行包含 n个整数

     

     

     

     

，表示整个数列   

   

   

   

。

输出格式

输出一个整数
  




  




  




  




  ，表示逆序对的个数     

     

     

     

     。

数据范围

1≤n≤100000 数列中的元素的取值范围 1∼10^9

输入样例： 62 3 4 5 6 1 输出样例： 5

思路讲解

首先还是理解下题意吧  


  


  


  


  

，通俗点讲 
     
     
     
     
，逆序对就是指

   




   




   




   




  ，一个数组中的两个数 



 



 



 



 

，如果前面的数大于后面的那个数                      ，那么这两个数就组成一个逆序对

求逆序对的算法是利用了分治的思想,在分治的过程中会将序列分为两部分


    




    




    




    




  ，此时逆序对可以分为三种情况：两个数都在左边的（设为s1）




  




  




  




  



。两个数都在右边的（s2）





















，一个数在左边一个数在右边的(s3)
  


  


  


  


。现在假设我们在归并排序的时候写的函数merge_sort(int[] q, int left, int right)可以返回l到r区间中逆序对数量     
     
     
     
    。那么s1便是左半边的返回值                       ，s2则是右半边的返回值


     



     



     



     



  ，而s3却无法如此得到




















，因为s3不知道跨度是什么 




   




   




   




   


。那么核心问题就在于怎么求s3   
    
    
    
    
，以及怎么使我们的merge_sort(int[] arr, int l, int r)可以返回l到r区间中逆序对数量

 



 



 



 



。

我们应当确定的是


     


     


     


     


 ，再归并排序中 




 




 




 




 ，其下等待归并的所有小数组   

   

   

   

   

，结尾有序数组

     

     

     

     

，也就是说
  




  




  




  




  ，若a数组中的a1大于b数组中的b1  


  


  


  


  

，那么a2 
     
     
     
     
，a3······都会是大于b1的

   




   




   




   




  ，那么我们就会很自然的得到res(最终结果)=mid-i+1                       。

而我们是如何得到情况s1和s2的呢？很显然的是 



 



 



 



 

，在递归过程中                      ，s1与s2其实是处于s3的状态的


    




    




    




    




  ，因此很轻易的就可以得到上述结论

需要强调的几点是

即使我们是求逆序对数量





















，也应当在排序后进行“扫尾    
    
    
    
 ”工作                       ，以确保后续递归的正常进行

由于我们求的是逆序对


     



     



     



     



  ，所以我们应当将方法返回值设为long类型




















，因为本题数据范围1≤n≤100000   
    
    
    
    
，若数组为降序数组


     


     


     


     


 ，int类型无法满足要求 




 




 




 




 ，应设置为long   

   

   

   

   

，

代码

import java.util.Scanner;​public class Main { //开辟足够大的数组空间 static int N = 100010; static int[] q = new int[N], temp = new int[N]; public static void main(String[] args) { //输入数组大小以及数组的值 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { q[i] = sc.nextInt(); }​ //运行方法并输出结果 System.out.println(merge_sort(q,0,n-1)); }​ public static long merge_sort(int []q,int left,int right) { //进行判断 if (left >= right) return 0;​ //进行递归

     

     

     

     

，将数组分为最小单位的值,接着在从最小进行排序
  




  




  




  




  ，逐渐到整个数组 int mid = left + (right - left) / 2;​ //确立返回值 long res = merge_sort(q,left,mid) + merge_sort(q,mid+1,right);​ int i = left, j = mid + 1;//建立双指针  


  


  


  


  

，i指向前一个数 
     
     
     
     
，j指向后一个数 int k = 0;//令temp从0开始

   




   




   




   




  ，往其中添加元素​ //进行归并操作 



 



 



 



 

，将数存放至临时数组temp while (i <= mid && j <= right) {//确认边界 if (q[i] <= q[j]) temp[k++] = q[i++]; else{ temp[k++] = q[j++]; res += mid - i + 1; } } //防止i或j提前用光的情况发生                      ，并保持后续数组排列正确 while (i <= mid) temp[k++] = q[i++]; while (j <= right) temp[k++] = q[j++];​ for(i = left,