# 0715. Range 模块 ### 题目地址(715. Range 模块) ### 题目描述 ``` 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 次。 ``` ### 前置知识 * 区间查找问题 * [二分查找](/leetcode-solution/91/binary-search.md) ### 公司 * 暂无 ### 二分法 #### 思路 直观的思路是使用端点记录已经被跟踪的区间，我们需要记录的区间信息大概是这样的：\[(1,2),(3,6),(8,12)]，这表示 \[1,2), \[3,6), \[8,12) 被跟踪。 添加区间需要先查一下会不会和已有的区间和交集，如果有则融合。删除区间也是类似。关于判断是否有交集以及融合都可以采用一次遍历的方式来解决，优点是简单直接。 区间查询的话，由于被跟踪的区间是有序且不重叠的（重叠的会被我们合并），因此可是使用二分查找来加速。 [官方给的解法](https://leetcode-cn.com/problems/range-module/solution/range-mo-kuai-by-leetcode/)其实就是这种。 代码： ```py class RangeModule(object): def __init__(self): # [(1,2),(3,6),(8,12)] self.ranges = [] def overlap(self, left, right): i, j = 0, len(self.ranges) - 1 while i < len(self.ranges) and self.ranges[i][1] < left: i += 1 while j >= 0 and self.ranges[j][0] > right: j -= 1 return i, j def addRange(self, left, right): i, j = self.overlap(left, right) if i <= j: left = min(left, self.ranges[i][0]) right = max(right, self.ranges[j][1]) self.ranges[i:j+1] = [(left, right)] def queryRange(self, left, right): i = bisect.bisect_right(self.ranges, (left, float('inf'))) - 1 return bool(self.ranges and self.ranges[i][0] <= left and right <= self.ranges[i][1]) def removeRange(self, left, right): i, j = self.overlap(left, right) merge = [] for k in xrange(i, j+1): if self.ranges[k][0] < left: merge.append((self.ranges[k][0], left)) if right < self.ranges[k][1]: merge.append((right, self.ranges[k][1])) self.ranges[i:j+1] = merge ``` 但其实这种做法 overlap 的时间复杂度是 $O(N)$，这部分可以优化。优化点点在于 overlap 的实现，实际上被跟踪的区间是有序的，因此这部分其实也可是二分查找。只不过我写了一半就发现不好根据结束时间查找。 参考了 [这篇题解](https://leetcode.com/problems/range-module/discuss/244194/Python-solution-using-bisect_left-bisect_right-with-explanation) 后发现，其实我们可以将被跟踪的区块一维化处理，这样问题就简单了。比如我们不这样记录被跟踪的区间 \[(1,2),(3,5),(8,12)]，而是这样：\[1,2,3,5,8,12]。 经过这样的处理， 数组的奇数坐标就是区间的结束点，偶数坐标就是开始点啦。这样二分就不需要像上面一样使用元组，而是使用单值了。 * 如何查询某一个区间 \[s, e] 是否被跟踪呢？我们只需要将 s， e 分别在数组中查一下。如果 s 和 e 都是**同一个奇数坐标**即可。 * 插入和删除也是一样。先将 s， e 分别在数组中查一下，假设我们查到的分别为 i 和 j，接下来使用 \[i, j] 更新原有区间即可。 ![示例1](https://p.ipic.vip/vmnsi6.jpg) ![示例2](https://p.ipic.vip/y8ii0o.jpg) 使用不同颜色区分不同的区间，当我们要查 \[3,9] 的时候。实线圈表示我们查到的索引，黑色的框框表示我们需要更新的区间。 区间更新逻辑如下： ![区间更新逻辑](https://p.ipic.vip/ovosah.jpg) #### 关键点解析 * 二分查找的灵活使用（最左插入和最右插入） * 将区间一维化处理 #### 代码 为了明白 Python 代码的含义，你需要明白 bisect\_left 和 bisect\_right，关于这两点我在[二分查找](/leetcode-solution/91/binary-search.md)专题讲地很清楚了，大家可以看一下。实际上这两者的区别只在于目标数组有目标值的情况，因此如果你搞不懂，可以尝试代入这种特殊情况理解。 代码支持：Python3 Python3 Code: ```py class RangeModule(object): def __init__(self): # [1,2,3,5,8,12] self.ranges = [] def overlap(self, left, right, is_odd): i = bisect_left(self.ranges, left) j = bisect_right(self.ranges, right) merge = [] if i & 1 == int(is_odd): merge.append(left) if j & 1 == int(is_odd): merge.append(right) # 修改 ranges 的 [i:j-1] 部分 self.ranges[i:j] = merge def addRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要保持不变， 就不难知道应该用 bisect_left 还是 bisect_right return self.overlap(left, right, False) def removeRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要为 [1,2,8,12]， 就不难知道应该用 bisect_left 还是 bisect_right return self.overlap(left, right, True) def queryRange(self, left, right): # [1,2,3,5,8,12]， 代入 left = 3, right = 5，此时需要返回 true， 就不难知道应该用 bisect_left 还是 bisect_right i = bisect_right(self.ranges, left) j = bisect_left(self.ranges, right) return i & 1 == 1 and i == 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: ```py class Node: 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 # 懒标记 class SegmentTree: def __init__(self,n): # 默认就一个根节点，不 build 出整个树，节省空间 self.root = Node(0,n-1) # 根节点 def update(self, l, r, v, node): if l > node.r or r < node.l: return if l <= node.l and node.r <= r: node.v = (node.r - node.l + 1) * v node.add = v # 做了一个标记 return self.__pushdown(node) # 动态开点。为子节点赋值，这个值就从 add 传递过来 if l <= node.m: self.update(l, r, v, node.left) if r > node.m: self.update(l, r, v, node.right) self.__pushup(node) # 动态开点结束后，修复当前节点的值 def query(self, l, r,node): if l > node.r or r < node.l: return False if l <= node.l and node.r <= r: return node.v == node.r - node.l + 1 self.__pushdown(node) # 动态开点。为子节点赋值，这个值就从 add 传递过来 ans = True if l <= node.m: ans = self.query(l, r, node.left) if ans and r > node.m: ans = self.query(l, r, node.right) return ans def __pushdown(self,node): if node.left is None: node.left = Node(node.l, node.m) if node.right is None: node.right = Node(node.m + 1, node.r) if node.add != -1: node.left.v = (node.left.r - node.left.l + 1) * node.add node.right.v = (node.right.r - node.right.l + 1) * node.add node.left.add = node.add node.right.add = node.add node.add = -1 def __pushup(self,node): node.v = node.left.v + node.right.v def updateSum(self,index,val): self.update(index,index,val,self.root) def querySum(self,left,right): return self.query(left,right,self.root) class RangeModule: def __init__(self): self.tree = SegmentTree(10 ** 9) def addRange(self, left: int, right: int) -> None: self.tree.update(left, right - 1, 1, self.tree.root) def queryRange(self, left: int, right: int) -> bool: return not not self.tree.querySum(left, right - 1) def removeRange(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 题解仓库： 。 目前已经 37K star 啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://p.ipic.vip/a21tbf.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/715.range-module.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.