715.range-module.md

题目地址(715. Range 模块)

https://leetcode-cn.com/problems/range-module/

题目描述

Range 模块是跟踪数字范围的模块。你的任务是以一种有效的方式设计和实现以下接口。 addRange(int left, int right) 添加半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。 queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true。 removeRange(int left, int right) 停止跟踪区间 [left, right) 中当前正在跟踪的每个实数。   示例： addRange(10, 20): null removeRange(14, 16): null queryRange(10, 14): true （区间 [10, 14) 中的每个数都正在被跟踪） queryRange(13, 15): false （未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字） queryRange(16, 17): true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）   提示： 半开区间 [left, right) 表示所有满足 left <= x < right 的实数。 对 addRange, queryRange, removeRange 的所有调用中 0 < left < right < 10^9。 在单个测试用例中，对 addRange 的调用总数不超过 1000 次。 在单个测试用例中，对  queryRange 的调用总数不超过 5000 次。 在单个测试用例中，对 removeRange 的调用总数不超过 1000 次。 

前置知识

• 区间查找问题
• 二分查找

公司

• 暂无

二分法

思路

直观的思路是使用端点记录已经被跟踪的区间，我们需要记录的区间信息大概是这样的：[(1,2),(3,6),(8,12)]，这表示 [1,2), [3,6), [8,12) 被跟踪。

添加区间需要先查一下会不会和已有的区间和交集，如果有则融合。删除区间也是类似。关于判断是否有交集以及融合都可以采用一次遍历的方式来解决，优点是简单直接。

区间查询的话，由于被跟踪的区间是有序且不重叠的（重叠的会被我们合并），因此可是使用二分查找来加速。

官方给的解法其实就是这种。

代码：

classRangeModule(object): def__init__(self): # [(1,2),(3,6),(8,12)]self.ranges= [] defoverlap(self, left, right): i, j=0, len(self.ranges) -1whilei<len(self.ranges) andself.ranges[i][1] <left: i+=1whilej>=0andself.ranges[j][0] >right: j-=1returni, jdefaddRange(self, left, right): i, j=self.overlap(left, right) ifi<=j: left=min(left, self.ranges[i][0]) right=max(right, self.ranges[j][1]) self.ranges[i:j+1] = [(left, right)] defqueryRange(self, left, right): i=bisect.bisect_right(self.ranges, (left, float('inf'))) -1returnbool(self.rangesandself.ranges[i][0] <=leftandright<=self.ranges[i][1]) defremoveRange(self, left, right): i, j=self.overlap(left, right) merge= [] forkinxrange(i, j+1): ifself.ranges[k][0] <left: merge.append((self.ranges[k][0], left)) ifright<self.ranges[k][1]: merge.append((right, self.ranges[k][1])) self.ranges[i:j+1] =merge

但其实这种做法 overlap 的时间复杂度是 $O(N)$，这部分可以优化。优化点点在于 overlap 的实现，实际上被跟踪的区间是有序的，因此这部分其实也可是二分查找。只不过我写了一半就发现不好根据结束时间查找。

参考了 这篇题解 后发现，其实我们可以将被跟踪的区块一维化处理，这样问题就简单了。比如我们不这样记录被跟踪的区间 [(1,2),(3,5),(8,12)]，而是这样：[1,2,3,5,8,12]。

经过这样的处理， 数组的奇数坐标就是区间的结束点，偶数坐标就是开始点啦。这样二分就不需要像上面一样使用元组，而是使用单值了。

• 如何查询某一个区间 [s, e] 是否被跟踪呢？我们只需要将 s， e 分别在数组中查一下。如果 s 和 e 都是同一个奇数坐标即可。
• 插入和删除也是一样。先将 s， e 分别在数组中查一下，假设我们查到的分别为 i 和 j，接下来使用 [i, j] 更新原有区间即可。

使用不同颜色区分不同的区间，当我们要查 [3,9] 的时候。实线圈表示我们查到的索引，黑色的框框表示我们需要更新的区间。

区间更新逻辑如下：

关键点解析

• 二分查找的灵活使用（最左插入和最右插入）
• 将区间一维化处理

代码

为了明白 Python 代码的含义，你需要明白 bisect_left 和 bisect_right，关于这两点我在二分查找专题讲地很清楚了，大家可以看一下。实际上这两者的区别只在于目标数组有目标值的情况，因此如果你搞不懂，可以尝试代入这种特殊情况理解。

代码支持：Python3

Python3 Code:

classRangeModule(object): def__init__(self): # [1,2,3,5,8,12]self.ranges= [] defoverlap(self, left, right, is_odd): i=bisect_left(self.ranges, left) j=bisect_right(self.ranges, right) merge= [] ifi&1==int(is_odd): merge.append(left) ifj&1==int(is_odd): merge.append(right) # 修改 ranges 的 [i:j-1] 部分self.ranges[i:j] =mergedefaddRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要保持不变， 就不难知道应该用 bisect_left 还是 bisect_rightreturnself.overlap(left, right, False) defremoveRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要为 [1,2,8,12]， 就不难知道应该用 bisect_left 还是 bisect_rightreturnself.overlap(left, right, True) defqueryRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要返回 true， 就不难知道应该用 bisect_left 还是 bisect_righti=bisect_right(self.ranges, left) j=bisect_left(self.ranges, right) returni&1==1andi==j# 都在一个区间内

addRange 和 removeRange 中使用 bisect_left 找到左端点 l，使用 bisect_right 找到右端点，这样将 [left, right) 更新到区间 [l, r - 1] 即可。

复杂度分析

• 时间复杂度：$O(logn)$，其中 n 为跟踪的数据规模
• 空间复杂度：$O(logn)$，其中 n 为跟踪的数据规模

动态开点线段树

思路

我们可以用线段树来解决区间更新问题。

由于数据规模很大， 因此动态开点就比较适合了。

插入的话就是区间 update 为 1， 删除就是区间 update 为 0，查找的话就看下区间和是否是区间长度即可。

代码为我的插件（公众号力扣加加回复插件可以获得）中提供的模板代码，稍微改了一下 query。这是因为普通的 query 是查找区间和， 而我们如果不修改， 那么会超时。我们的区间和可以提前退出。如果区间和不等于区间长度就提前退出即可。

代码

代码支持：Python3

Python3 Code:

classNode: def__init__(self, l, r): self.left=None# 左孩子的指针self.right=None# 右孩子的指针self.l=l# 区间左端点self.r=r# 区间右端点self.m= (l+r) >>1# 中点self.v=0# 当前值self.add=-1# 懒标记classSegmentTree: def__init__(self,n): # 默认就一个根节点，不 build 出整个树，节省空间self.root=Node(0,n-1) # 根节点defupdate(self, l, r, v, node): ifl>node.rorr<node.l: returnifl<=node.landnode.r<=r: node.v= (node.r-node.l+1) *vnode.add=v# 做了一个标记returnself.__pushdown(node) # 动态开点。为子节点赋值，这个值就从 add 传递过来ifl<=node.m: self.update(l, r, v, node.left) ifr>node.m: self.update(l, r, v, node.right) self.__pushup(node) # 动态开点结束后，修复当前节点的值defquery(self, l, r,node): ifl>node.rorr<node.l: returnFalseifl<=node.landnode.r<=r: returnnode.v==node.r-node.l+1self.__pushdown(node) # 动态开点。为子节点赋值，这个值就从 add 传递过来ans=Trueifl<=node.m: ans=self.query(l, r, node.left) ifansandr>node.m: ans=self.query(l, r, node.right) returnansdef__pushdown(self,node): ifnode.leftisNone: node.left=Node(node.l, node.m) ifnode.rightisNone: node.right=Node(node.m+1, node.r) ifnode.add!=-1: node.left.v= (node.left.r-node.left.l+1) *node.addnode.right.v= (node.right.r-node.right.l+1) *node.addnode.left.add=node.addnode.right.add=node.addnode.add=-1def__pushup(self,node): node.v=node.left.v+node.right.vdefupdateSum(self,index,val): self.update(index,index,val,self.root) defquerySum(self,left,right): returnself.query(left,right,self.root) classRangeModule: def__init__(self): self.tree=SegmentTree(10**9) defaddRange(self, left: int, right: int) ->None: self.tree.update(left, right-1, 1, self.tree.root) defqueryRange(self, left: int, right: int) ->bool: returnnotnotself.tree.querySum(left, right-1) defremoveRange(self, left: int, right: int) ->None: self.tree.update(left, right-1, 0, self.tree.root) # Your RangeModule object will be instantiated and called as such:# obj = RangeModule()# obj.addRange(left,right)# param_2 = obj.queryRange(left,right)# obj.removeRange(left,right)

复杂度分析

• 时间复杂度：$O(logn)$，其中 n 为跟踪的数据规模
• 空间复杂度：$O(logn)$，其中 n 为跟踪的数据规模

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。