[LeetCode]Rectangle Area II

这道题Brute Force的做法不难想，我们把矩形分解成1x1的小矩形，用一个二维数组表示对应的单位矩形是否出现过，然后算总面积即可。但是显而易见这个方法时间复杂度过于高，并不适用。
但是这个方法可以提供一个很好的思路，我们可以把输入的点压缩一下来优化一下时间复杂度。比如说如果x轴上的点出现了[2, 5, 30, 200, 3200]，我们可以将其映射到[0, 1, 2, 3, 4]的区间，这样我们仍然是算有多少个1x1个小矩形，但是算面积的时候，再把对应[1, N]区间的数map回原坐标计算面积即可。假设输入有N个矩形，时间复杂度O(N^3)，空间复杂度O(N^2), 代码如下：



除此之外，如果我们想象一根平行于x轴的直线从最底端向上扫，我们可以得到所有矩形在不同y坐标下在x轴的映射。我们可以根据每个单位长度y下，矩形在x轴上映射的长度的和来算出总的矩形的面积。所以现在的问题是，如果算出矩形在x轴上的映射，Segment Tree可以帮助我们解决这类区间问题。
首先我们的关心的是range，所以叶节点也是range，也就是说我们的叶节点是类似[1, 2], [2, 3]这种而不是之前有的题目我们会存的[1, 1]，[2, 2]。其次就是我们在每一个node上存什么，这里有多种思路。首先我们要知道的是每个区间有多长被cover了，记作coveredRange。但是我们不能直接存这个，比如我们插入了两次[1, 3]，之后又删除了[1, 3]一次，这时候[1, 3]仍然是被完全覆盖的，但是只存coveredRange的话我们是没法检测这种情况的。所以我们转而存当前区间被完全覆盖的次数，因为我们需要区间更新，所以我们采用lazy propagation的实现方式，具体查看上面的文章。更新的话按部就班，查询的话如果当前区间被完全覆盖了我们直接return对应的的range，否则递归查询左右两个子区间。这里我们仍然要用index compression来压缩输入x和y的范围，我们可以去重也可以不去重，不会影响结果。时间复杂度O(N log N)，空间复杂度O(N)，代码如下：



官方给出的segment tree是另外一种存的方式，每个节点存了两个变量：

• 当前区间被覆盖的长度，coveredRange
• 输入区间能被分解成当前区间的次数cnt。比如[1, 4]，假设可以分解为[1, 3]和[3, 4]，这两个区间对应线段树里的两个node，我们把对应node的cnt数加1，而[1, 3]的子区间[1, 2]和[2, 3]我们不管。也就是说这里的cnt和上面的不太一样，不再具有父区间cnt的改变一定会影响到子区间的性质，反之亦然。这里每个node对应的cnt是相互独立的。

那么我们查询和更新的时候就可以根据这两个变量来进行操作。时间复杂度空间复杂度相同，代码如下：