一道OJ题：https://leetcode.com/problems/count-of-smaller-numbers-after-self/
1.暴力
时间复杂度O(n^2)
2.归并排序
O(nlog(n))
在合并的过程中是将两个相邻并且有序的序列合并成一个有序序列，如以下两个有序序列
Seq1：3 4 5
Seq2：2 6 8 9
合并成一个有序序:
Seq：2 3 4 5 6 8 9
对于序列seq1中的某个数a[i],序列seq2中的某个数a[j]，如果a[i]<a[j],没有逆序数，如果a[i]>a[j]，那么逆序数为seq1中a[i]后边元素的个数(包括a[i])，即len1-i+1,
这样累加每次递归过程的逆序数，在完成整个递归过程之后，最后的累加和就是逆序的总数
3.更加trick的方法,线段树
O(nlog(n))
方法3：用树状数组
还是以刚才的序列
3 5 4 8 2 6 9
大体思路为：新建一个数组，将数组中每个元素置0
0 0 0 0 0 0 0
取数列中最大的元素，将该元素所在位置置1
0 0 0 0 0 0 1
统计该位置前放置元素的个数，为0
接着放第二大元素8，将第四个位置置1
0 0 0 1 0 0 1
统计该位置前放置元素的个数，为0
继续放第三大元素6，将第六个位置置1
0 0 0 1 0 1 1
统计该位置前放置元素的个数，为1
…
…
这样直到把最小元素放完，累加每次放元素是该元素前边已放元素的个数，这样就算出总的逆序数来了
在统计和计算每次放某个元素时，该元素前边已放元素的个数时如果一个一个地数，那么一趟复杂度为O(n),总共操作n趟，复杂度为O(n^2)，和第一种方法的复杂度一样了，那我们为什么还用这么复杂的方法
当然，在每次统计的过程中用树状数组可以把每一趟计数个数的复杂度降为O(logn)，这样整个复杂度就变为O(nlogn)
原文：http://www.cnblogs.com/huangshiyu13/p/5789673.html