树状数组求逆序对
【转载注明出处】
给一个例子：
5 2 1 4 3
在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。
1，输入5， 调用upDate(5, 1),把第5位设置为1
1 2 3 4 5
0 0 0 0 1
计算1-5上比5小的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，
现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。
2. 输入2， 调用upDate(2, 1),把第2位设置为1
1 2 3 4 5
0 1 0 0 1
计算1-2上比2小的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，
现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。
3. 输入1， 调用upDate(1, 1),把第1位设置为1
1 2 3 4 5
1 1 0 0 1
计算1-1上比1小的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，
现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。
4. 输入4， 调用upDate(4, 1),把第5位设置为1
1 2 3 4 5
1 1 0 1 1
计算1-4上比4小的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，
现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。
5. 输入3， 调用upDate(3, 1),把第3位设置为1
1 2 3 4 5
1 1 1 1 1
计算1-3上比3小的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，
现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。
6. 0+1+2+1+2 = 6 这就是最后的逆序数
分析一下时间复杂度，首先用到快速排序，时间复杂度为O(NlogN),
后面是循环插入每一个数字，每次插入一个数字，分别调用一次upData()和getSum()
外循环N, upData()和getSum()时间O(logN) => 时间复杂度还是O(NlogN).
最后总的还是O(NlogN).
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
