algorithm - 如何为每个元组计算数组中严格更大的元组的数量？

Question

假设您有一个带有变量 a 和 b 的 Pair 类。

当 a 和 b 值都大于另一个对象时，Pair 对象“严格大于”另一个对象。例如，(3,4) 会大于 (2,3)，但 (3,5) 不会大于 (4,4) 等等。

给定一个 Pair 数组，计算数组中每个元素的严格大于 Pair 数量的最佳方法是什么？我可以在 n^2 内解决这个问题，但我认为这不是最佳答案。

Answer 1

根据 a 变量对 Pair 进行排序；这将花费 O(nlogn) 时间。然后使用一些自平衡二叉树结构(红黑、AVL 等)从你的对中构建一个线段树，以 b 变量作为它的键，节点子树的大小为它的值(value)。这也将花费 O(nlogn) 时间。

现在，遍历已排序的 Pair 数组。对于每一对，首先在线段树中定位相应的节点，并计算来自该节点及其祖先的值/大小的具有较大b的Pair的总数。将其添加到运行总和中，然后从树中删除该节点。每个 Pair 应该花费 O(logn) 时间。对数组中的所有其他 Pair 继续此过程。最后，您的运行总和将代表数组中严格大于对象的总数，耗时 O(nlogn)。