> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/intervals/715.-range-module.md).

# 715. Range Module

给定一系列interval，实现对它们的添加，查询(给定Interval是否完全包括在已有内)和删除。在对interval操作后把有重叠的合并并保证interval有序后，查询直接二分定位到和input 有overlap的那个interval。同样添加和删除也是在查询到overlap interval后做合并，添加是合并后把合并的插入，删除是把overlap都删除，再补上两端可能多删的。查询overlap参考了花花的[实现](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DpcpB9ux3RrQ)，非常精妙。根据\[left, right]查overlap得到两个interval iterator l和r, 保证\[left,right]一定在\[l,r)内。这样当l == r时说明\[left, right]和已有Intervals无交集。

```cpp
/*
 * @lc app=leetcode id=715 lang=cpp
 *
 * [715] Range Module
 */

// @lc code=start
class RangeModule {
public:
    map<int, int> ranges;
    typedef map<int, int>::iterator IT;
    inline void overlapRanges(const int left, const int right, IT &l, IT &r) {
        // interval中第一个比left和right大的start
        l = ranges.upper_bound(left);
        r = ranges.upper_bound(right);
        // [left, right] 一定在[l, r)内
        if (l != ranges.begin()) {
            if (prev(l)->second >= left) {
                --l;
            }
        }
    }

    RangeModule() {}
    
    void addRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        if (l != r) {
            auto last = r;
            --last;
            left = min(left, l->first);
            right = max(right, last->second);
            ranges.erase(l, r);
        }
        ranges[left] = right;
    }
    
    bool queryRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        // 左闭右开，相等说明无overlap.
        if (l == r) return false;
        // 是否全部包含在了l里。
        return l->first <= left && l->second >= right;
    }
    
    void removeRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        if (l == r) return;
        auto last = r;
        --last;
        int start = min(left, l->first);
        int end = max(right, last->second);
        // 删掉所有overlap的ranges
        ranges.erase(l, r);
        // 补上可能多删掉的
        if (start < left) ranges[start] = left;
        if (end > right) ranges[right] = end;
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */
// @lc code=end


```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/intervals/715.-range-module.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.