我正在寻找任何可以帮助我解决这个问题的提示。我尝试了几种启发式方法——例如,在考虑从底向上的方式解决这个问题时,对于一个固定的节点v,v.left和v.right可以为v提供某种集合(平衡BST?),其中操作bigger(x)会对于给定的x在logarithmic时间内返回该集合中大于x的元素数量。问题在于,我们需要在O(log n)中合并这些集合,因此似乎行不通,因为我不知道任何有序集合数据结构支持快速合并。
我还考虑了自上而下的方法——如果仅当u位于到根路径的简单路径上且u < v时,节点v才会向某个u.bigger添加1。因此,v可以以某种方式更新所有这些u,但是我无法想出任何合理的方法来做到这一点...
那么,解决这个问题的正确方法是什么?