[2022-06-20]715. Range 模块👋设计👋线段树👋有序集合

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/range-module

难度: Hard
标签: 设计 线段树 有序集合

[dreamjean]

715. Range 模块

Description

Difficulty: 困难

Related Topics: 设计, 线段树, 有序集合

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⁴ 次

Solution

Language: JavaScript

var RangeModule = function() {
    this.intervals = [];
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.addRange = function(left, right) {
    const intv = this.intervals;
    let newInterval = [left, right];
    let i = 0;

    // 遍历 intervals 找到要插入的位置
    while (i < intv.length && intv[i][1] < newInterval[0]) i++;

    // 将所有重叠的区间合并到同一个区间 
    while (i < intv.length && intv[i][0] <= newInterval[1]) {
        newInterval = [Math.min(newInterval[0], intv[i][0]), Math.max(newInterval[1], intv[i][1])];
        intv.splice(i, 1); // 删除被合并的区间
    }

    // 将新区间加入 intervals
    intv.splice(i, 0, newInterval);
};

 /** 
 * @param {number} left 
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function(left, right) {
    const intv = this.intervals;
    let [low, high] = [0, intv.length - 1];
    while (low <= high) {
        const mid = (low + high) >>> 1;
        if (intv[mid][0] <= left && intv[mid][1] >= right) return true;

        if (intv[mid][0] > left) high = mid - 1;
        else low = mid + 1;
    }

    return false;
};   

/** 
 * @param {number} left 
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function(left, right) {
    const intv = this.intervals;
    let i = 0;
    while (i < intv.length && intv[i][1] < left) i++;
    
    if (i < intv.length && intv[i][0] < left) {
        let newIntervalBefore = [intv[i][0], left];

        // 要删除的区间在其中一个区间内
        if (right < intv[i][1]) {
            let newIntervalAfter = [right, intv[i][1]];
            intv.splice(i, 1, newIntervalBefore, newIntervalAfter);
            return;
        }

        intv.splice(i, 1, newIntervalBefore);
        i++;
    }
    
    while (i < intv.length && right >= intv[i][1]) intv.splice(i, 1);

    if (i < intv.length && right > intv[i][0]) {
        let newIntervalAfter = [right, intv[i][1]];
        intv.splice(i, 1, newIntervalAfter);
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */