利用线段树求逆序数（JAVA）
设A是一个包含n个不同数的数组。如果在i<j的情况下，有A>A，则（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 > arr){
++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;
}
}
先以区间为根节点建立val都为0的线段树,
再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间已插入的节点数(如果存在,必与1构成逆序)v1=0
在线段树中插入3, 插入之前先询问区间已插入的节点数(如果存在,必与3构成逆序)v2=0
在线段树中插入6, 插入之前先询问区间已插入的节点数(如果存在,必与6构成逆序)v3=0
在线段树中插入9, 插入之前先询问区间已插入的节点数(如果存在,必与9构成逆序)v4=0
在线段树中插入0, 插入之前先询问区间已插入的节点数(如果存在,必与0构成逆序)v5=4
在线段树中插入8, 插入之前先询问区间已插入的节点数(如果存在,必与8构成逆序)v6=1
在线段树中插入5, 插入之前先询问区间已插入的节点数(如果存在,必与5构成逆序)v7=3
在线段树中插入7, 插入之前先询问区间已插入的节点数(如果存在,必与7构成逆序)v8=2
在线段树中插入4, 插入之前先询问区间已插入的节点数(如果存在,必与4构成逆序)v9=5
在线段树中插入2, 插入之前先询问区间已插入的节点数(如果存在,必与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]+up])，low]表示比a小的数
//在0-（n-1）序列里low]=a,up]=n-a-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;//用数组实现线段树 for(int i=0;i<16370;i++) tt=new Seg_Tree(); } private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树tt.left = left;tt.right = right;tt.val = 0;if(left == right) return ;int mid = tt.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 =.val=1 .val=2.val=1.val=3.val=1.val=5.val=1 .val=2.val=1.val=10.val=1.val=2.val=1 .val=3.val=1.val=5.val=1.val=2.val=1 */ private void insert(int aim,int l,int r,int k){//将aim插入到线段树 if(tt.left==aim&&tt.right==aim) { tt.val++;return ; } if(aim<=tt.calmid()) insert(aim,l,tt.calmid(),LL(k)); else insert(aim,tt.calmid()+1,r,2*k+1); tt.val=tt.val+tt.val; } public void printTree(int i){//中序遍历线段树 if(2*i>16370) return; printTree(2*i); if(tt.right!=0) System.out.print("["+tt.left+","+tt.right+"]"+".val="+tt.val+"");//注意，没有输出 printTree(2*i+1); } //查询中已插入的节点数 private int query(int left,int right,int idx){if(left == tt.left && right == tt.right) return tt.val;int mid = tt.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;ma.build(0,n-1,1);int sum = 0; for(int i=0;i<n;i++){ val=in.nextInt(); sum += ma.query(val,n-1,1);//先查询 ma.insert(val,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 + (n - val - 1);ret=Math.min(ret,sum);} System.out.println(ret); } }}
源码:
页:
[1]