LeetCode 题解工作台
Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。 半开区间 [left, right) 表示所有 left 的实数 x 。 实现 RangeModule 类: RangeModule() 初始化数据结构的对象。 void addRange(int lef…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · design·结合·segment·树
答案摘要
根据题目描述，我们需要维护一个区间集合，支持区间的添加、删除和查询操作。对于区间的添加和删除操作，我们可以使用线段树来维护区间集合。 线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 design·结合·segment·树 题型思路
题目描述
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule()初始化数据结构的对象。void addRange(int left, int right)添加 半开区间[left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间[left, right)中尚未跟踪的任何数字到该区间中。boolean queryRange(int left, int right)只有在当前正在跟踪区间[left, right)中的每一个实数时，才返回true，否则返回false。void removeRange(int left, int right)停止跟踪 半开区间[left, right)中当前正在跟踪的每个实数。
示例 1：
输入 ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] 输出 [null, null, null, true, false, true] 解释 RangeModule rangeModule = new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪） rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字） rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
提示：
1 <= left < right <= 109- 在单个测试用例中，对
addRange、queryRange和removeRange的调用总数不超过104次
解题思路
方法一：线段树
根据题目描述，我们需要维护一个区间集合，支持区间的添加、删除和查询操作。对于区间的添加和删除操作，我们可以使用线段树来维护区间集合。
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 ；
- 线段树的每个叶子节点代表一个长度为 的元区间 ；
- 对于每个内部节点 ，它的左儿子是 ，右儿子是 , 其中 (即向下取整)。
由于题目数据范围较大，我们可以使用动态开点的线段树来实现。动态开点的线段树是指，我们只在需要的时候才开点，而不是一开始就开好所有的点。这样可以节省空间，但是需要使用懒标记来维护区间修改。
时间复杂度方面，每次操作的时间复杂度为 。空间复杂度为 。其中 为操作次数，而 为数据范围。
class Node:
__slots__ = ['left', 'right', 'add', 'v']
def __init__(self):
self.left = None
self.right = None
self.add = 0
self.v = False
class SegmentTree:
__slots__ = ['root']
def __init__(self):
self.root = Node()
def modify(self, left, right, v, l=1, r=int(1e9), node=None):
if node is None:
node = self.root
if l >= left and r <= right:
if v == 1:
node.add = 1
node.v = True
else:
node.add = -1
node.v = False
return
self.pushdown(node)
mid = (l + r) >> 1
if left <= mid:
self.modify(left, right, v, l, mid, node.left)
if right > mid:
self.modify(left, right, v, mid + 1, r, node.right)
self.pushup(node)
def query(self, left, right, l=1, r=int(1e9), node=None):
if node is None:
node = self.root
if l >= left and r <= right:
return node.v
self.pushdown(node)
mid = (l + r) >> 1
v = True
if left <= mid:
v = v and self.query(left, right, l, mid, node.left)
if right > mid:
v = v and self.query(left, right, mid + 1, r, node.right)
return v
def pushup(self, node):
node.v = bool(node.left and node.left.v and node.right and node.right.v)
def pushdown(self, node):
if node.left is None:
node.left = Node()
if node.right is None:
node.right = Node()
if node.add:
node.left.add = node.right.add = node.add
node.left.v = node.add == 1
node.right.v = node.add == 1
node.add = 0
class RangeModule:
def __init__(self):
self.tree = SegmentTree()
def addRange(self, left: int, right: int) -> None:
self.tree.modify(left, right - 1, 1)
def queryRange(self, left: int, right: int) -> bool:
return self.tree.query(left, right - 1)
def removeRange(self, left: int, right: int) -> None:
self.tree.modify(left, right - 1, -1)
# 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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Let |
| 空间 | O(A+R) |
面试官常问的追问
外企场景- question_mark
The candidate should demonstrate understanding of range operations and how segment trees or ordered sets can optimize range tracking.
- question_mark
Watch for solutions that optimize for time complexity, especially during range queries.
- question_mark
Look for insights into managing disjoint intervals and minimizing redundant work during add and remove operations.
常见陷阱
外企场景- error
Mismanaging the disjoint intervals can lead to inefficient queries, making the solution suboptimal.
- error
Not utilizing binary search or sorted data structures properly could cause unnecessary linear time operations for queryRange.
- error
Adding or removing ranges without maintaining the disjoint property of intervals can result in incorrect coverage during queries.
进阶变体
外企场景- arrow_right_alt
Allow for dynamic resizing of the range boundaries.
- arrow_right_alt
Extend the problem to handle overlapping ranges more efficiently.
- arrow_right_alt
Modify the solution to handle interval modifications instead of simple add/remove operations.