715 Range 模块（set维护区间的动态信息）

墨蓝 2022-09-09 09:28 120阅读 0赞

**1. 问题描述：**

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）  
链接：https://leetcode-cn.com/problems/range-module

**2. 思路分析：**

分析题目可以知道涉及到**区间修改**和**区间查询**，所以我们可以使用带有懒标记的线段树来解决，但是带有懒标记的线段树比较复杂（线段树一般能够解决10 ^ 5之内的数据范围的题目），考虑到数据范围不是特别大我们可以使用c++中的set集合来维护区间的动态信息，set集合的一个好处是能够在插入元素的时候维护一个有序的集合，并且集合中的所有元素都是不重复的，set集合的元素为Pair类型，这样可以维护每一个区间。初始化的时候我们可以先加入两个正无穷与负无穷的边界，这样后面在查找元素的时候会比较好处理不用判断边界的情况。添加一个区间到集合中的时候我们可以在S中找到一个区间t使得t的左端点大于等于l（使用lower\_bound函数查找），这样区间t的上一个区间的左端点小于left，然后我们需要根据这个位置找出所有与当前区间相交的区间然后删除这些区间，最后加入合并的区间（在删除之前计算合并区间的左右端点）；删除区间也是类似的，也是需要找到第一个与当前区间有交集的区间然后从这个位置开始删除所有与当前区间有交集的区间，最后加上删除之后剩下来的区间即可；查找区间是否存在的时候我们可以先找到第一个大于当前区间的区间，判断这个区间的上一个区间的右端点是否大于right即可，画图比较容易写出具体的代码，感觉这道题目使用python的数据结构处理就很麻烦使用c++语言来处理会比较简单一点。(也可以使用带有懒标记的线段树使用动态开点的写法来解决的)

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_8_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

#include<iostream>
    #include<set>
    #include<vector>
    using namespace std;
    typedef pair<int, int> PII;
    #define x first
    #define y second
    const int INF = 2e9;
    
    
    class RangeModule {
    public:
        set<PII> S;
        RangeModule() {
            // 插入两个边界
            S.insert({-INF, -INF});
            S.insert({INF, INF});
        }
        
        void addRange(int left, int right) {
            auto i = S.lower_bound({left, -INF});
            // i--之后i为上一个区间
            i--;
            // 上一个区间与当前区间没有交集那么看下一个区间
            if (i->y < left) i++;
            // 下一个区间没有交集那么直接插入
            if (i->x > right) S.insert({left, right});
            else{
                auto j = i;
                // 暴力寻找所有与当前区间有交集的区间
                while (right >= j->x) j++;
                j--;
                // 先计算出合并之后区间的左右端点
                PII t(min(left, i->x), max(right, j->y));
                // 删除与当前区间[left, right]有交集的部分
                while (i != j)
                {
                    auto k = i;
                    k++;
                    S.erase(i);
                    i = k;
                }
                // 移除掉当前有交集的最后一个区间
                S.erase(i);
                S.insert(t);
            }
        }
        
        // 查询区间[left, right)是否存在
        bool queryRange(int left, int right) {
            
            auto i = S.upper_bound({left, INF});
            i--;
            return i->y >= right;
        }
        
        // 删除区间的过程与插入区间的过程是类似的, 删除区间也是删除所有与当前区间有交集的区间然后加入剩余的未删除的区间
        void removeRange(int left, int right) {
            auto i = S.lower_bound({left, -INF});
            i--;
            if (i->y < left) i ++;
            if (i->x <= right){
                auto j = i;
                while (j->x <= right) j++;
                j--;
                // 求解当前删除区间之后的剩余的区间
                auto a = get(*i, {left, right});
                auto b = get(*j, {left, right});
                while (i != j)
                {
                    auto k = i;
                    k++;
                    S.erase(i);
                    i = k;
                }
                S.erase(i);
                for (auto t: a) S.insert(t);
                for (auto t: b) S.insert(t);
            }
        }
        
        // 合并未删除的区间
        vector<PII> get(PII a, PII b){
            vector<PII> res;
            if (a.x < b.x){
                if (a.y > b.y){
                    res.push_back({a.x, b.x});
                    res.push_back({b.y, a.y});
                }else res.push_back({a.x, b.x});
            }else{
                if (a.y > b.y)res.push_back({b.y, a.y});
            }
            return res;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/85d54e38c6664581b10204e1b43aa83e.png