题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
知识引入
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 O ( log N ) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用Lazy标记时，标记也要满足可加性
注：可加性表示运算能否合并，例如取模就不满足可加性，对4 取模然后对 3 取模，两个操作就不能合并在一起做。
线段树是平衡二叉树，依然可以用数组表示。对于满二叉树最后一层(h-1)的节点数(2^(h-1))等于前面所有层的节点数之和，对于n个元素，需要长度为4n的数组表示。
解题思路
代码实现
class Solution {
public int reversePairs(int[] nums) {
int count = 0;
Map<Integer, Integer> ranks = getRanks(nums);
int length = nums.length;
SegmentTree st = new SegmentTree(length);
for (int i = 0; i < length; i++) {
int rank = ranks.get(nums[i]);
count += st.getCount(rank + 1, length - 1);
st.add(rank);
}
return count;
}
public Map<Integer, Integer> getRanks(int[] nums) {
int length = nums.length;
int[] sorted = new int[length];
System.arraycopy(nums, 0, sorted, 0, length);
Arrays.sort(sorted);
Map<Integer, Integer> ranks = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++) {
int num = sorted[i];
if (i == 0 || num > sorted[i - 1]) {
ranks.put(num, i);
}
}
return ranks;
}
}
class SegmentTree {
int length;
int[] tree;
public SegmentTree(int length) {
this.length = length;
this.tree = new int[length * 4];
}
public int getCount(int start, int end) {
return getCount(start, end, 0, 0, length - 1);
}
public void add(int rank) {
add(rank, 0, 0, length - 1);
}
private int getCount(int rangeStart, int rangeEnd, int index, int treeStart, int treeEnd) {
if (rangeStart > rangeEnd) {
return 0;
}
if (rangeStart == treeStart && rangeEnd == treeEnd) {
return tree[index];
}
int mid = treeStart + (treeEnd - treeStart) / 2;
if (rangeEnd <= mid) {
return getCount(rangeStart, rangeEnd, index * 2 + 1, treeStart, mid);
} else if (rangeStart > mid) {
return getCount(rangeStart, rangeEnd, index * 2 + 2, mid + 1, treeEnd);
} else {
return getCount(rangeStart, mid, index * 2 + 1, treeStart, mid) + getCount(mid + 1, rangeEnd, index * 2 + 2, mid + 1, treeEnd);
}
}
//给定某个值，更新对应区间的的数据量
private void add(int rank, int index, int start, int end) {
if (start == end) {
tree[index]++;
return;
}
int mid = start + (end - start) / 2;
if (rank <= mid) {
add(rank, index * 2 + 1, start, mid);
} else {
add(rank, index * 2 + 2, mid + 1, end);
}
tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2];
}
}