是否存在时间复杂度低于O(n²)的算法求解数组元素对计数问题

存在，可实现*O(n log n)*的时间复杂度，远优于O(n²)。

算法核心思路 #

该问题本质是逆序对统计的变种，核心逻辑如下：

• 提前根据公式B_i = x * A_i + y算出所有B的取值，该逻辑不受x、y的取值影响
• 从右到左遍历数组，动态维护下标大于当前j的所有A元素的有序集合
• 对每个j，快速查询有序集合中大于B_j的元素数量，累加到总结果中，再将当前A_j插入有序集合
• 每次查询和插入操作的时间复杂度为O(log n)，整体遍历n次，总时间复杂度为O(n log n)

具体实现方案 #

方案1：树状数组/线段树实现（推荐，常数更低） #

如果数值范围较大，先做离散化处理压缩取值范围：

1. 收集所有A_i和B_i的取值，去重后升序排序，映射为1~m的连续下标（m≤2n）
2. 初始化空的树状数组，从数组末尾开始倒序遍历每个下标j：
   • 查询树状数组中大于B_j对应下标的元素总和，累加到最终结果
   • 将A_j对应下标位置的计数+1，更新树状数组

方案2：平衡二叉搜索树实现 #

可直接调用语言内置的有序集合结构实现，代码更简洁：

• 例如C++的std::multiset、Java的TreeSet都自带范围查询接口
• 倒序遍历时调用upper_bound类接口快速查询大于B_j的元素数量，再插入A_j即可

示例验证 #

用题目给出的输入做验证，A = [3,1,5,7]，x=1、y=2，对应B = [5,3,7,9]：

1. j=3，右侧无元素，累加0，插入7，有序集合为{7}，总结果=0
2. j=2，B_j=7，查询大于7的元素数量为0，累加0，插入5，有序集合为{5,7}，总结果=0
3. j=1，B_j=3，查询大于3的元素数量为2，累加2，插入1，有序集合为{1,5,7}，总结果=2
4. j=0，B_j=5，查询大于5的元素数量为1，累加1，插入3，有序集合为{1,3,5,7}，总结果=3
   和题目给出的输出结果完全一致。

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