> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0715-range-module.md).

# 0715. Range Module

<https://leetcode.com/problems/range-module>

## Description

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as **half-open intervals** and query about them.

A **half-open interval** `[left, right)` denotes all the real numbers `x` where `left <= x < right`.

Implement the `RangeModule` class:

* `RangeModule()` Initializes the object of the data structure.
* `void addRange(int left, int right)` Adds the **half-open interval** `[left, right)`, tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval `[left, right)` that are not already tracked.
* `boolean queryRange(int left, int right)` Returns `true` if every real number in the interval `[left, right)` is currently being tracked, and `false` otherwise.
* `void removeRange(int left, int right)` Stops tracking every real number currently being tracked in the **half-open interval** `[left, right)`.

**Example 1:**

```
**Input**
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
**Output**
[null, null, null, true, false, true]
**Explanation**
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
```

**Constraints:**

* `1 <= left < right <= 109`
* At most `104` calls will be made to `addRange`, `queryRange`, and `removeRange`.

## ac

```java
class RangeModule {
    TreeMap<Integer, Integer> tmap;
    public RangeModule() {
        tmap = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        // clean
        clean(left, right);

        Integer floor = tmap.floorKey(left);
        Integer ceil = tmap.ceilingKey(right);
        if (floor == null || tmap.get(floor) == 1) {
            tmap.put(left, 0); // add start point
        }
        if (ceil == null || tmap.get(ceil) == 0) {
            tmap.put(right, 1);
        }
    }

    public boolean queryRange(int left, int right) {
        Integer floor = tmap.floorKey(left);
        if (floor == null || tmap.get(floor) != 0) return false;

        Map<Integer, Integer> sub = tmap.subMap(left, false, right, false);

        return sub.size() == 0;

    }

    public void removeRange(int left, int right) {
        clean(left, right);

        Integer floor = tmap.floorKey(left);
        Integer ceil = tmap.ceilingKey(right);
        if (floor != null && tmap.get(floor) == 0) {
            tmap.put(left, 1);
        }
        if (ceil != null && tmap.get(ceil) == 1) {
            tmap.put(right, 0);
        }
    }

    public void clean(int left, int right) {
        Map<Integer, Integer> sub = tmap.subMap(left, true, right, true);
        Set<Integer> set = new HashSet<>(sub.keySet());
        tmap.keySet().removeAll(set);
    }
}

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

/*
1) treemap record start/end point; 2) add/remove, clean first, then add start/end point;
*/
```