如何使用范围树解决这个问题？

Question

问题：

我们在位面中获得了 n 件宝藏 t1, ..., tn。每个宝藏

ti

都有一个相关的价值

vi

。你的任务是设计一个返回轴对齐

k × k

正方形位置的算法最大化其中所含宝藏的总价值。

你的算法最多应该在 O(n^2\log^2n) 时间和空间内运行（即，独立于 k 并且 k 不是常数）。和往常一样，也证明正确性并分析运行时间和空间。为了简单起见，您可以假设没有两个宝藏具有相同的 x 或 y 坐标。

如何使用范围树解决这个问题？据我所知，我们可以根据宝藏的坐标构建一个二维范围树。然后我们需要进行范围查询并在这些查询中找到最佳结果（总价值）。我知道如何在范围树上查询，我的困惑是我们应该把查询放在哪里？

Answer 1

给定一个包含最佳宝藏集合的最佳矩形，您可以将其向下移动，而不降低其价值，直到顶部边缘与其中一个宝藏相遇。

同样，您可以将其向右移动，而不减少其价值，直到左边缘遇到其中一个宝藏。

因此，存在一个左边缘和上边缘都与宝藏相交的最佳矩形。这样的矩形最多有 n² 个，每个矩形代表一种方式，即你可以从一个宝藏中选取 x 坐标作为左边缘，从一个宝藏中选取 y 坐标作为上边缘。

这些是您应该测试的矩形。