题意:给定很多个(大概100个)矩形,的左上角右下角坐标(不一定为整数),要求它们的面积的并。

分析:这道题的数据非常水,只是test case可能会比较多。所以 O(n3) 爆力过不了。只能想想有没有 O(n2log2n) 或者更低的复杂度的算法。很幸运,有两种可行办法(应该说我只想到了这两种):第一种是结合扫描线的 O(nlog2n) 的算法。第二种是二维线段树,复杂度为约 O(nlog2n) 其中第一种方案的空间复杂度为 O(nlog2n) ,第二种为 O(n2log2n) 。由于数据水的原因,我采用了比较容易想的第二种方案。并且考虑到网上关于二维线段树的题解不多,大量的扫描线,我更坚定了实现二维线段树的信念。

实现:二维线段树的实现很简单,也就是把线段树的两个子节点改成了四个。当然,其时间空间复杂度都会比普通线段树有所增加。下面求其最坏情况下单次操作的时间复杂度。

设一棵二维线段树描述的是一个n*n的矩形。则它有logn层。

若第i层选取了k个节点。则第(i+1)层最多可以选取2*k+12个节点。(显然)若第三层选取了中心的4个节点,则第logn层选取了约2^(logn)个节点。由此推知,二维线段树的最坏单次操作时间复杂度O(n)。所以方案二的最坏时间复杂度可以退化为O(n2),但是对于本题,足矣!

其实二维线段树的用法还不止这种不中用的地方。在二维碰撞检测、矩阵操作等方面它都有用武之地。不多说,上代码。

纪念以下这道水过的水题