beileye521的博客

原创 IndexedTree 解决逆序对个数

IndexTree 解决逆序对个数 首先将原序列按照降序排序，依次放入indexTree数组中。 由于先放入的数值是大的，后放入的数字是小的，因此计算逆序对个数时，只需要在更新indexTree的时候，查询当前下标之前有几个数字，这里用1来计数。 构建indexTree数组。由于indexTree数组模拟的是完美二叉树格式。如下图： 那么，根据测试用例5 3 2 4 1 构造的indexTree 模型如下图： ...