树状数组求逆序对个数（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,