如何用范围树解决最大价值k×k轴对齐正方形问题？

问题描述 #

平面上给定n个宝藏$t_1, \dots, t_n$，每个宝藏$t_i$关联价值$v_i$。需设计算法找到轴对齐的k×k正方形位置，使其中包含的宝藏总价值最大。要求算法的时间与空间复杂度不超过$O(n^2 \log^2 n)$（k为非常数且与复杂度无关），可假设任意两个宝藏的x或y坐标均不相同。

核心困惑 #

已知可基于宝藏坐标构建二维范围树，通过范围查询获取区域内的总价值，但不清楚应如何设定查询范围才能覆盖所有可能的最优正方形。

解决方案 #

查询范围的核心设定逻辑 #

最优的k×k轴对齐正方形，其边界必然经过至少一个宝藏的坐标（x或y方向）。原因是：若某个正方形的所有边界都不经过任何宝藏坐标，可将其平移至边界碰到某个宝藏坐标，平移过程中不会改变包含的宝藏集合（因所有坐标互不相同），总价值保持不变——这意味着最优解一定能在边界经过宝藏坐标的正方形中找到。

基于此，查询范围的设定规则为：

• 取任意宝藏的x坐标作为正方形的左边界，对应右边界为$x + k$；
• 取任意宝藏的y坐标作为正方形的下边界，对应上边界为$y + k$；
• 所有由上述x/y边界组合成的矩形区域（即k×k正方形），就是需要查询的范围集合。

完整算法步骤 #

1. 预处理坐标排序：将所有宝藏的x坐标升序排序得到$X = [x_1, x_2, \dots, x_n]$，y坐标升序排序得到$Y = [y_1, y_2, \dots, y_n]$。
2. 构建二维范围树：基于宝藏的(x,y)坐标和价值$v_i$构建二维范围树，树的每个节点存储对应区域内的宝藏总价值，支持$O(\log^2 n)$时间复杂度的矩形区域总价值查询。
3. 枚举所有候选正方形并查询：
   • 遍历每个宝藏的x坐标$x_i$作为正方形左边界，计算右边界$x_i + k$；
   • 对每个上述x范围，遍历每个宝藏的y坐标$y_j$作为正方形下边界，计算上边界$y_j + k$；
   • 用范围树查询矩形$[x_i, x_i+k] \times [y_j, y_j+k]$内的总价值，记录所有查询结果中的最大值。

正确性证明 #

假设存在一个最优正方形$S$，其所有边界均不经过任何宝藏坐标。将$S$向左平移，直到左边界碰到某个宝藏的x坐标$x_i$，得到新正方形$S'$。由于所有宝藏的x坐标均不等于$S$的原左边界，平移过程中没有宝藏进入或离开$S$，因此$S'$的总价值与$S$相同，也是最优解。同理，若平移至右边界碰到某个x坐标，或上下边界碰到y坐标，也能得到等价的最优正方形。因此，枚举所有边界经过宝藏坐标的正方形，必然能找到最优解。

复杂度分析 #

• 预处理排序：$O(n \log n)$，仅需对x、y坐标各排序一次。
• 范围树构建：时间复杂度$O(n \log n)$，空间复杂度$O(n \log n)$，符合二维范围树的标准复杂度。
• 枚举与查询：共需枚举$n \times n$个候选正方形，每个查询的时间复杂度为$O(\log^2 n)$，因此总时间复杂度为$O(n^2 \log^2 n)$，满足题目要求。
• 总空间复杂度：$O(n \log n)$，远低于$O(n^2 \log^2 n)$的上限。

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