如何解决加权优势计数问题？d维场景下是否存在O(n log^d(n))时间解法？

答案是可以，d维加权优势计数问题确实可以在O(n log^d n)的时间复杂度下求解。

加权优势计数问题的核心规则：对于d维空间中的两个点a=(a₁,a₂,…,a_d)和b=(b₁,b₂,…,b_d)，称a支配b当且仅当对所有1≤i≤d，均满足a_i ≤ b_i（若要求严格支配只需调整为a_i < b_i，不影响复杂度结论）。我们需要对每个点p，统计所有支配p的点的权重总和。

低维场景验证 #

• 1维场景：将所有点按坐标升序排序，遍历过程中用前缀和或Fenwick树（树状数组）累加已遍历点的权重，查询当前点的对应权重和即可，时间复杂度为O(n log n) = O(n log^1 n)，符合复杂度公式。
• 2维场景：先对所有点按第一维坐标升序排序，保证遍历到当前点时，所有已处理点的第一维都满足支配条件，再用Fenwick树维护第二维坐标对应的权重和，每次查询第二维≤当前点的权重总和即可，时间复杂度为O(n log² n)，同样匹配公式。

高维场景推广 #

对于d≥3的场景，可以通过分层分治降维的思路实现：

1. 先对所有点在第1维上排序，消除第1维的支配判断约束，将问题转化为d-1维的加权优势计数问题。
2. 对剩下的d-1维递归使用相同的降维逻辑，每一层处理一个维度，每层的时间复杂度为O(n log n)。
3. 共需要d层处理，总时间复杂度为O(n log^d n)。

也可以采用d层嵌套的Fenwick树实现，每个点的查询和更新操作复杂度为O(log^d n)，n个点的总复杂度同样符合要求。

补充说明 #

如果点的坐标范围过大，可以预先对每个维度的坐标做离散化处理，该操作的时间复杂度为O(d n log n)，不会改变原有的复杂度阶数。对于坐标相等的边界场景，只需调整排序时的优先级规则即可，也不会额外增加时间开销。

内容的提问来源于stack exchange，提问作者高翔宇