给定数组A，如何求每个元素A[i]前比它小的元素数，有优于O(n²)的算法吗？

当然存在比朴素O(n²)更优的算法，时间复杂度可以做到O(n log n)，最常用的实现方案是树状数组（Binary Indexed Tree, BIT），其次也可以用归并排序的变种实现。

树状数组实现思路 #

我们的核心需求是两个：动态维护已经遍历过的元素集合，快速查询集合中小于当前元素的总个数，树状数组可以把这两个操作的耗时都降到O(log n)级别，整体复杂度就是O(n log n)。
具体步骤如下：

1. 离散化处理：如果数组元素的数值范围很大（比如存在1e9级别的值），直接用数值当下标开数组会浪费空间，所以先把数组所有元素去重后从小到大排序，把每个元素映射为1~m的连续整数（m是去重后的元素总数，最大等于n）。
   比如示例数组A = [1,2,3,2,1]，去重排序后得到[1,2,3]，映射关系为1→1、2→2、3→3。
2. 遍历+查询+更新：从左到右遍历原数组，对每个元素x：

• 先查询树状数组中[1, rank(x)-1]的前缀和，这个结果就是当前元素前面所有小于它的元素总数，存入结果数组
• 再把树状数组中rank(x)对应的位置计数+1，代表当前元素已经加入已遍历集合

以示例数组验证执行过程：

最终得到结果[0,1,2,1,0]，和预期完全一致。

归并排序变种实现思路 #

和求解逆序对的思路类似，在归并排序的合并阶段统计数值：归并时左右两个子数组都是有序的，且左子数组所有元素的原始下标都小于右子数组，对于右子数组的每个元素，可以快速统计左子数组中小于它的元素个数，累加到对应原始下标的结果中即可。这种方法不需要做离散化，适合元素是浮点数等不方便做离散映射的场景，时间复杂度同样是O(n log n)。

内容的提问来源于stack exchange，提问作者Michael