Links

0715. Range 模块

题目地址(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) 被跟踪。
添加区间需要先查一下会不会和已有的区间和交集,如果有则融合。删除区间也是类似。关于判断是否有交集以及融合都可以采用一次遍历的方式来解决,优点是简单直接。
区间查询的话,由于被跟踪的区间是有序且不重叠的(重叠的会被我们合并),因此可是使用二分查找来加速。
官方给的解法其实就是这种。
代码:
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 的实现,实际上被跟踪的区间是有序的,因此这部分其实也可是二分查找。只不过我写了一半就发现不好根据结束时间查找。
参考了 这篇题解 后发现,其实我们可以将被跟踪的区块一维化处理,这样问题就简单了。比如我们不这样记录被跟踪的区间 [(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
示例2
使用不同颜色区分不同的区间,当我们要查 [3,9] 的时候。实线圈表示我们查到的索引,黑色的框框表示我们需要更新的区间。
区间更新逻辑如下:
区间更新逻辑

关键点解析

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

代码

为了明白 Python 代码的含义,你需要明白 bisect_left 和 bisect_right,关于这两点我在二分查找专题讲地很清楚了,大家可以看一下。实际上这两者的区别只在于目标数组有目标值的情况,因此如果你搞不懂,可以尝试代入这种特殊情况理解。
代码支持:Python3
Python3 Code:
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:
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 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。