范围查询的另一解法需要借助范围树（range tree)。为此，首先仿照如图8.37（教材240页)和图8.38（教

范围查询的另一解法需要借助范围树(range tree)。

为此，首先仿照如图8.37(教材240页)和图8.38(教材241页)所示的策略，按x坐标将平面上所有输入点组织为一棵平衡二叉搜索树，称作主树(main tree)。

于是如图x8.10(a)和(b)所示，该树中每个节点各自对应于一个竖直的条带区域;左、右孩子所对应的条带互不重叠，均由父节点所对应的条带垂直平分而得;同一深度上所有节点所对应的条带也互不重叠，而且它们合并后恰好覆盖整个平面。

接下来，分别对于主树中每一节点，将落在其所对应条带区域中的输入点视作一个输入子集，并同样采用以上方法，按照y坐标将各个子集组织为一棵平衡二叉搜索树，它们称作关联树(associative tree)。于是如图x8.10(a)和(c)所示，每棵关联树所对应的竖直条带，都会进而逐层细分为多个矩形区域，且这些矩形区域也同样具有以上所列主树中各节点所对应条带区域的性质，至此，主树与这o(n)棵关联树构成了一个两层的嵌套结构，即所谓的范围树。

利用范围树，可按如下思路实现高效的范围查询，对于任一查询范围R=[x₁，x₂]×[y₁，y₂]，首先按照[x₁，x₂]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x₁，x₂]范围内的所有输入点。

接下来，深入这些节点各自对应的关联树，分别按照[y₁，y₂]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y₁，y₂]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。

a)试证明，如此实现的范围树，空间复杂度为o(nlogn);

b)按照以上描述，试利用你的范围树实现新的范围查询算法;

c)试证明，以上范围查询算法的时间复杂度为O(r+log²n)，其中r为实际命中并被报告的点数;

d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。