设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的逆序数了.