利用线段树求逆序数（JAVA）

   设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j]，则（i，j）就称为A中的一个逆序对（inversion）

   现给出一个数列，求该数列中的逆序对数（逆序数）。最直接的暴力方法；
  两层for循环就可以算出来逆序数：每遇到一个元素回头遍历寻找比其大的元素个数即可，
  当然向后寻找比其小的元素个数也可以，复杂度为O(n^2)，代码：

   int sum = 0;
   for(int i = 0; i < size; ++i) {
      for(int j = i+1; j < size; ++j){
         if(arr[i] > arr[j]){
             ++sum;
         }
     }
  }
  return sum;


下面方法用线段树,逆序数就是一个“区间和”的问题：
对于数列中的每个元素，它对应的逆序数便是之前序列中大于该元素的元素个数和。

由于线段树的插入和查询操作皆可以在lgn的时间内完成，故遍历一个数列求逆序数的时间复杂度为O(nlgn)

例:HDU1394
    给你一个数字组成的序列，然后进行这样的操作，每次将最前面一个元素放到最后面去会得到一个序列，
那么这样就形成了n个序列，那么每个序列都有一个逆序数，找出其中最小的一个输出！
样例:
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16

分析:

线段树节点这样定义：
class Seg_Tree {//线段树节点
int left,right;
        int val;//区间内已插入的节点数
int calmid() {
return (left+right)/2;
}
   }

先以区间[0,9]为根节点建立val都为0的线段树, 
  
再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间[1,9]已插入的节点数(如果存在,必与1构成逆序)  v1=0
在线段树中插入3, 插入之前先询问区间[3,9]已插入的节点数(如果存在,必与3构成逆序)  v2=0
在线段树中插入6, 插入之前先询问区间[6,9]已插入的节点数(如果存在,必与6构成逆序)  v3=0
在线段树中插入9, 插入之前先询问区间[9,9]已插入的节点数(如果存在,必与9构成逆序)  v4=0
在线段树中插入0, 插入之前先询问区间[0,9]已插入的节点数(如果存在,必与0构成逆序)  v5=4
在线段树中插入8, 插入之前先询问区间[8,9]已插入的节点数(如果存在,必与8构成逆序)  v6=1
在线段树中插入5, 插入之前先询问区间[5,9]已插入的节点数(如果存在,必与5构成逆序)  v7=3
在线段树中插入7, 插入之前先询问区间[7,9]已插入的节点数(如果存在,必与7构成逆序)  v8=2
在线段树中插入4, 插入之前先询问区间[4,9]已插入的节点数(如果存在,必与4构成逆序)  v9=5
在线段树中插入2, 插入之前先询问区间[2,9]已插入的节点数(如果存在,必与2构成逆序)  v10=7
累加v1+……+v10  =22，这就是1 3 6 9 0 8 5 7 4 2的逆序数了.


这题要把第一个数放到最后
3 6 9 0 8 5 7 4 2 1
这样就增加了9个逆序,其逆序为22+9=31
6 9 0 8 5 7 4 2 1 3
这样增加了6个,减少了3个,其逆序数为31+6-3=34;
............
//公式：第一个数移到最后位置后逆序数
//sum=sum+(-low[a[i]]+up[a[i]])，low[a[i]]表示比a[i]小的数
//在0-（n-1）序列里low[a[i]]=a[i],up[a[i]]=n-a[i]-1;

最后AC过的代码:

 import java.util.Scanner;

     class Seg_Tree {//线段树节点
	int left,right;
        int val;//区间内已插入的节点数
	int calmid() {
		return (left+right)/2;
	}
   }

  public class Main{
     private int LL(int x) { return x<<1;}  //两倍；
     private int RR(int x) { return x<<1|1;} //两倍+1；
     Seg_Tree tt[];
 

    public Main(){
      tt=new Seg_Tree[16370];//用数组实现线段树
      for(int i=0;i<16370;i++)
          tt[i]=new Seg_Tree();
    }

    private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].val = 0;
	if(left == right) return ;	
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
    }
   
   /*  如果将节点全部插入,应该是下面结果:
     C:\java>java Main
     10
     1 3 6 9 0 8 5 7 4 2
   [0,0]=.val=1 [0,1].val=2  [1,1].val=1  [0,2].val=3  [2,2].val=1  [0,4].val=5  [3,3].val=1  
    [3,4].val=2  [4,4].val=1  [0,9].val=10  [5,5].val=1  [5,6].val=2  [6,6].val=1  
    [5,7].val=3  [7,7].val=1  [5,9].val=5  [8,8].val=1  [8,9].val=2  [9,9].val=1
   */
    
   private void insert(int aim,int l,int r,int k){  //将aim插入到线段树
    if(tt[k].left==aim&&tt[k].right==aim) {
      tt[k].val++;return ;
    }  
  
    if(aim<=tt[k].calmid()) 
       insert(aim,l,tt[k].calmid(),LL(k));  
    else     
      insert(aim,tt[k].calmid()+1,r,2*k+1);  
    tt[k].val=tt[LL(k)].val+tt[RR(k)].val;  
  }  

    public void printTree(int i){//中序遍历线段树
      if(2*i>16370) return;
      printTree(2*i);
      if(tt[i].right!=0) System.out.print("["+tt[i].left+","+tt[i].right+"]"+".val="+tt[i].val+"  ");//注意，没有输出[0，0]
      printTree(2*i+1);
      
    }
       
  
   

    //查询[left，right]中已插入的节点数
    private int query(int left,int right,int idx){
	if(left == tt[idx].left && right == tt[idx].right) 
           return tt[idx].val;
	
	int mid = tt[idx].calmid();
	if(right <= mid){
		return query(left,right,LL(idx));
	} 
       else if(mid < left) {
		return query(left,right,RR(idx));
	} 
       else {
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
	}
     }


  

     public static void main(String[] args){
        Scanner in=new Scanner(System.in);
	int n;
	while(in.hasNext()) {
          n=in.nextInt();
          Main ma=new Main();
          int val[]=new int[n];
	  ma.build(0,n-1,1);
	  int sum = 0;	
          for(int i=0;i<n;i++){
            val[i]=in.nextInt();
            sum += ma.query(val[i],n-1,1);//先查询
            ma.insert(val[i],0,n-1,1);//后插入
	   }
         // ma.printTree(1);
         // System.out.println();//中序遍历线段树
        //  System.out.println(sum);
	   int ret = sum;
	
        for(int i=0;i<n;i++){
	  sum = sum - val[i] + (n - val[i] - 1);
	  ret=Math.min(ret,sum);
	}
	 System.out.println(ret);
         
	}
       
   }
}

源码: