Range 模块

难度: Hard

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 <= 10⁹
在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 10⁴ 次

Submission

运行时间: 194 ms

内存: 20.9 MB

import bisect
class RangeModule:

    def __init__(self):
        self.intervals = []
        # numbers [l1, r1, l2, r2, ..., ln, rn]

    def addRange(self, left: int, right: int) -> None:
        # [l1, r1, l2, r2, ..., ln, rn]
        # r < left <= l, r <= right < l
        left_ind = bisect.bisect_left(self.intervals, left)
        right_ind = bisect.bisect_right(self.intervals, right)
        tmp = []
        if left_ind % 2 == 0: tmp.append(left)
        if right_ind % 2 == 0: tmp.append(right)
        self.intervals[left_ind:right_ind] = tmp

    def queryRange(self, left: int, right: int) -> bool:
        # [l1, r1, l2, r2, ..., ln, rn]
        # l <= left < r, l < right <= r
        left_ind = bisect.bisect_right(self.intervals, left)
        right_ind = bisect.bisect_left(self.intervals, right)
        if left_ind == right_ind and left_ind % 2 == 1:
            return True
        return False
 
    def removeRange(self, left: int, right: int) -> None:
        # [l1, r1, l2, r2, ..., ln, rn]
        # l <= left < r, l < right <= r
        left_ind = bisect.bisect_right(self.intervals, left)
        right_ind = bisect.bisect_left(self.intervals, right)
        tmp = []
        if left_ind % 2 == 1: tmp.append(left)
        if right_ind % 2 == 1: tmp.append(right)
        self.intervals[left_ind:right_ind] = tmp

# 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)

Explain

这道题的题解使用了一个数组 intervals 来存储所有的区间端点。将每个区间 [left, right) 表示为两个数 left 和 right，并保存在 intervals 数组中。偶数下标代表区间的左端点，奇数下标代表区间的右端点。在 addRange、queryRange 和 removeRange 操作中，利用二分查找确定区间的插入位置或判断区间是否存在，并对 intervals 数组进行相应的修改。

时间复杂度: O(log n) 到 O(n)

空间复杂度: O(n)

import bisect
class RangeModule:

    def __init__(self):
        self.intervals = []  # 存储区间端点的数组
        # numbers [l1, r1, l2, r2, ..., ln, rn]

    def addRange(self, left: int, right: int) -> None:
        # [l1, r1, l2, r2, ..., ln, rn]
        # r < left <= l, r <= right < l
        left_ind = bisect.bisect_left(self.intervals, left)  # 二分查找左端点的插入位置
        right_ind = bisect.bisect_right(self.intervals, right)  # 二分查找右端点的插入位置
        tmp = []
        if left_ind % 2 == 0: tmp.append(left)  # 如果左端点下标为偶数，则将左端点加入 tmp 数组
        if right_ind % 2 == 0: tmp.append(right)  # 如果右端点下标为偶数，则将右端点加入 tmp 数组
        self.intervals[left_ind:right_ind] = tmp  # 将 tmp 数组替换 intervals 数组中对应的部分

    def queryRange(self, left: int, right: int) -> bool:
        # [l1, r1, l2, r2, ..., ln, rn]
        # l <= left < r, l < right <= r
        left_ind = bisect.bisect_right(self.intervals, left)  # 二分查找左端点的插入位置
        right_ind = bisect.bisect_left(self.intervals, right)  # 二分查找右端点的插入位置
        if left_ind == right_ind and left_ind % 2 == 1:  # 如果左右端点下标相等且为奇数，则区间存在
            return True
        return False
 
    def removeRange(self, left: int, right: int) -> None:
        # [l1, r1, l2, r2, ..., ln, rn]
        # l <= left < r, l < right <= r
        left_ind = bisect.bisect_right(self.intervals, left)  # 二分查找左端点的插入位置
        right_ind = bisect.bisect_left(self.intervals, right)  # 二分查找右端点的插入位置
        tmp = []
        if left_ind % 2 == 1: tmp.append(left)  # 如果左端点下标为奇数，则将左端点加入 tmp 数组
        if right_ind % 2 == 1: tmp.append(right)  # 如果右端点下标为奇数，则将右端点加入 tmp 数组
        self.intervals[left_ind:right_ind] = tmp  # 将 tmp 数组替换 intervals 数组中对应的部分

# 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)

Explore

在`addRange`方法中，`left_ind`为偶数意味着`left`位置在现有区间之外，即`left`不在任何现有的左闭右开区间内。此时，`left`作为新区间的起始端点，需要被添加到表示区间的`intervals`数组中。如果`left_ind`是奇数，则`left`已经位于某个现有区间内，因此不需要将其作为新的起始端点加入。这种处理确保了区间的正确表示，避免了区间的重复或错误扩展。

在`queryRange`方法中，`left_ind`等于`right_ind`且为奇数时返回`true`的逻辑基于数组`intervals`的偶奇下标规则，其中偶数下标表示区间的开始，奇数下标表示区间的结束。当`left_ind`和`right_ind`相等且为奇数时，这表示查询的区间`[left, right)`完全位于一个已存在的区间内部，因为奇数下标的位置是区间的结束位置。这种判断确保了查询的区间完全被某个已有区间覆盖。

在`removeRange`方法中，基于原端点下标的奇偶性来决定是否将新的端点加入`tmp`数组是为了确保正确处理区间的修改。如果`left_ind`是奇数，表示`left`位于某个区间内部，因此需要在`left`处断开这个区间，将`left`作为新的结束点。同理，如果`right_ind`是奇数，则`right`也位于某个区间内部，需要将`right`作为新的开始点，从而在`right`处断开区间。这样的处理方式使得区间能够精确地被修改或删除指定的部分。

在处理`addRange`和`removeRange`时，边界情况需特别注意。对于`addRange`，如果添加的区间完全覆盖现有一个或多个区间，通过`left_ind`和`right_ind`的计算，可以确定覆盖范围，并将此区间范围内的所有端点从`intervals`中删除，只保留新区间的边界。对于`removeRange`，如果移除的区间仅部分与现有区间重叠，同样通过`left_ind`和`right_ind`确定影响的范围，并适当地调整或分割现有区间，确保区间的连续性和准确性。这些操作确保了区间数组的正确性和最优表示。