范围树：为什么不默认保存 space？
Range Trees: why not save space by default?
假设您在二维平面上有一组 S 个唯一点。现在，您期待着 "is point p present in S?" 形式的一堆问题 您决定构建一个范围树来存储您的 S 并回答这个问题。 Range Tree 背后的基本思想是，首先在 0-th 坐标上构建一个平衡二叉搜索树 Tree0，然后在 Tree0 的每个节点构建另一个平衡搜索树 Tree1 但这次使用 1-st 坐标作为键。 Wikipedia article for Range Tree.
现在，我期望为 Tree0 的每个节点 n0 构建的 Tree1 将准确保存那些 0-th 坐标等于键的点来自 n0。但是，如果您阅读更多有关 Range Trees 的内容，您会发现情况并非如此。具体来说：
Tree0 的根 r0 包含一个包含所有点的 Tree1。r0 的左边 child 包含一个 Tree1，它包含 0-th 坐标小于 0-th 坐标的所有点 r0.r0右边的child包含一个Tree1，它包含所有0-th坐标大于r0坐标的点。
如果继续这个逻辑，您将看到在范围树的每一层，所有点都只存储一次。因此，每个级别都需要 n 内存，并且由于平衡 Tree0 的深度是 logn，因此需要 O(nlogn) 作为内存要求。
但是，如果您只存储 0-th 坐标 与节点处的键 完全匹配的点，那么您将为整个树存储每个点一次（而不是树的每个级别），这给出了 O(n) 内存要求。
在范围树中每个级别存储一次点的原因是什么？它是否允许某种很酷的范围查询之类的？到目前为止，在我看来，您可以在 O(nlogn) 版本上执行的任何查询也可用于 O(n) 版本。我错过了什么？
（将@user3386109 的评论扩展为完整答案。）
有几种不同的数据结构用于存储点的二维集合，每种数据结构都针对不同类型的查询进行了优化。顾名思义，范围树针对 范围搜索进行了优化， 形式的查询“这是一个矩形，该矩形中的所有点是什么？”范围树的结构 - 将每个点存储在几个不同的子树中 - 旨在让您可以在一维中找到包含矩形的一个轴的节点跨度，然后发现下一维中位于另一个维度中的所有节点的矩形。如果您不打算对该表单进行任何查询，则无需以这种方式存储内容。您实际上是在为您不会使用的东西付费。
还有其他数据结构可用于存储一组点并查看特定点是否存在。如果这是您需要回答的唯一问题，那么您可能只需要使用一个简单的散列 table。您还可以使用常规 BST，其中点首先通过它们的第一个组件进行比较，然后通过它们的第二个组件进行比较。 （如果你愿意，你也可以在这里使用 k-d 树。）
希望对您有所帮助！
假设您在二维平面上有一组 S 个唯一点。现在，您期待着 "is point p present in S?" 形式的一堆问题 您决定构建一个范围树来存储您的 S 并回答这个问题。 Range Tree 背后的基本思想是，首先在 0-th 坐标上构建一个平衡二叉搜索树 Tree0，然后在 Tree0 的每个节点构建另一个平衡搜索树 Tree1 但这次使用 1-st 坐标作为键。 Wikipedia article for Range Tree.
现在，我期望为 Tree0 的每个节点 n0 构建的 Tree1 将准确保存那些 0-th 坐标等于键的点来自 n0。但是，如果您阅读更多有关 Range Trees 的内容，您会发现情况并非如此。具体来说：
Tree0的根r0包含一个包含所有点的Tree1。r0的左边 child 包含一个Tree1，它包含0-th坐标小于0-th坐标的所有点r0.r0右边的child包含一个Tree1，它包含所有0-th坐标大于r0坐标的点。
如果继续这个逻辑，您将看到在范围树的每一层，所有点都只存储一次。因此，每个级别都需要 n 内存，并且由于平衡 Tree0 的深度是 logn，因此需要 O(nlogn) 作为内存要求。
但是，如果您只存储 0-th 坐标 与节点处的键 完全匹配的点，那么您将为整个树存储每个点一次（而不是树的每个级别），这给出了 O(n) 内存要求。
在范围树中每个级别存储一次点的原因是什么？它是否允许某种很酷的范围查询之类的？到目前为止，在我看来，您可以在 O(nlogn) 版本上执行的任何查询也可用于 O(n) 版本。我错过了什么？
（将@user3386109 的评论扩展为完整答案。）
有几种不同的数据结构用于存储点的二维集合，每种数据结构都针对不同类型的查询进行了优化。顾名思义，范围树针对 范围搜索进行了优化， 形式的查询“这是一个矩形，该矩形中的所有点是什么？”范围树的结构 - 将每个点存储在几个不同的子树中 - 旨在让您可以在一维中找到包含矩形的一个轴的节点跨度，然后发现下一维中位于另一个维度中的所有节点的矩形。如果您不打算对该表单进行任何查询，则无需以这种方式存储内容。您实际上是在为您不会使用的东西付费。
还有其他数据结构可用于存储一组点并查看特定点是否存在。如果这是您需要回答的唯一问题，那么您可能只需要使用一个简单的散列 table。您还可以使用常规 BST，其中点首先通过它们的第一个组件进行比较，然后通过它们的第二个组件进行比较。 （如果你愿意，你也可以在这里使用 k-d 树。）
希望对您有所帮助！