恩 而且二维线段树也是 log n 时间

矩形重叠的情况 应该可以直接用 二维线段树吧 ？ 那样的话 连扫描排序都不用了 呵呵。


不过有个问题。。。会不会占用太多的空间了。。
因为一开始并不清楚 每个立方体到底会被分到什么位置。。。所以不能很好的确定每个数的边界
一维情况可以先扫描一遍，确定有哪些分隔点。
但是二维情况如果要节省空间的话，
第二维的划分是附属在第一维情况下的，即在第一维的不同位置处第二维的划分方式不同。然而这一步的实现需要的时间能不能保证在 n log n 呢？
如果在第一维的不同位置 第二维的 划分方法都一样的话，那就会要 n*n 的储存空间了

我在想:拓展到 m 维的话有没有什么通法？（线段树 占的空间随 m 指数增大阿）

二维应该也可以离散化，空间需求的确是指数增长了

我想到一种方法： 空间上和m是线性的 但是时间上就不知道了。。。。。（但肯定不会超过 n^2)

是这样的，由于如果重叠的话，两个立方体 应该要在所有的维度上 都重叠，所一如下设计：

首先，还是对 x轴扫描，排序。 ------------ n log n
然后建立 y 轴的 和 z 轴的 两个树。（这个树上面提到过，这里是只能提供判断功能的简化版）
每个节点上只有一个位置所标，和一该节点为根的子树的节点数。
那么每次插入位置时就可以知道该节点在树中的序号（位置重合就放在一个节点上，节点数+1，重合的节点考虑序号时考虑边界条件）。
每次加入线段时，将两个点分别加入（线段中位置靠前的点先加入，以免后加入的点影响前一个点的序号） ---------log n
然后看线段中两个点的序号，如果不连续，那么其中就有别的点，序号之差就是其中的其他的节点的个数。 ------------ 1
分别计算 y 轴 和 x 轴的情况。取其中所夹的节点数 较少的 那个轴，对所夹的节点作遍历，依次比较其所在立方体是否与插入的立方体重合。 --------- ？
程序运行完 还没有重叠的情况的话，就是没有了。

其实还可以 直接建立 x y z 轴的三个树。每次全部插入（就没有删除了），取最少的所夹节点做依次比较。


这个方法所用空间的话 应该是 m*n 的空间，时间是 n log n + n *(log n +1 + ?)

关键是其中的 ？ 应该是多少.....能不能控制在 log n 时间里呢？


加我qq啊！ 我给你发了短消息了。

O(n^2)的算法很容易得到，任意枚举两个几何体判断是否相交就好了

那个方法好像 ? 所需的时间确实是 n 时间
不过可以有效地降低 n 的系数 呵呵 ， 而且m 越大 其系数越小

我再想想有没有什么好的办法吧。。。。