# Range Module
**Difficulty:** HARD
[External](https://leetcode.com/problems/range-module)
Canonical: https://scaleengineer.com/dsa/problems/range-module
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Segment Tree, Ordered Set
**Companies:** [Coupang](https://scaleengineer.com/companies/coupang), [Machine Zone](https://scaleengineer.com/companies/machine-zone)
---
## Problem
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`.

# Approaches
## Sorted List of Intervals
This approach maintains a sorted list of disjoint intervals. Operations like adding or removing a range require iterating through the list to find affected intervals, merging or splitting them, and then creating a new list with the updated intervals. While modifications are slow, querying can be made efficient using binary search.
**Time:** `addRange`: O(N)
`removeRange`: O(N)
`queryRange`: O(log N)

Where N is the number of disjoint intervals. `addRange` and `removeRange` must scan the entire list. · **Space:** O(N), where N is the number of disjoint intervals. In the worst case, N can be up to the number of calls.
**Pros:** Relatively simple to understand and implement.; The `queryRange` operation is efficient (`O(log N)`) due to binary search.
**Cons:** The `addRange` and `removeRange` operations are inefficient, requiring a full scan and recreation of the list, leading to `O(N)` time complexity.; Rebuilding the list in modification operations can lead to higher memory usage and garbage collection overhead.
### Explanation
We use a `java.util.ArrayList<int[]>` to store the intervals, kept sorted by their start times.

`addRange(left, right)`: We build a new list by iterating through the old one. We copy over intervals that come before the new range. Then, we merge the new range `[left, right)` with all overlapping intervals from the old list into a single new interval. Finally, we add this merged interval and any remaining intervals from the old list to our new list. The old list is then replaced by the new one. This process takes linear time with respect to the number of intervals.

`removeRange(left, right)`: Similar to `addRange`, we create a new list. We iterate through the old list. For each interval, if it doesn't overlap with `[left, right)`, we add it to the new list. If it does overlap, we calculate the parts of the interval that remain after the removal and add them as new, smaller intervals to the new list. This also takes linear time.

`queryRange(left, right)`: Since the list is sorted by the start time, we can use binary search to efficiently find an interval that could potentially cover the query range `[left, right)`. We search for the interval with the largest start time that is less than or equal to `left`. If such an interval exists and its end time is greater than or equal to `right`, the query is satisfied. This is a logarithmic time operation.

```java
class RangeModule {
    List<int[]> intervals;

    public RangeModule() {
        intervals = new ArrayList<>();
    }

    public void addRange(int left, int right) {
        List<int[]> newIntervals = new ArrayList<>();
        boolean inserted = false;
        for (int[] interval : intervals) {
            if (interval[1] < left) {
                newIntervals.add(interval);
            } else if (interval[0] > right) {
                if (!inserted) {
                    newIntervals.add(new int[]{left, right});
                    inserted = true;
                }
                newIntervals.add(interval);
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!inserted) {
            newIntervals.add(new int[]{left, right});
        }
        intervals = newIntervals;
    }

    public boolean queryRange(int left, int right) {
        int low = 0, high = intervals.size() - 1;
        int idx = -1;
        // Binary search to find an interval that might contain [left, right)
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(intervals.get(mid)[0] <= left){
                idx = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return idx != -1 && intervals.get(idx)[1] >= right;
    }

    public void removeRange(int left, int right) {
        List<int[]> newIntervals = new ArrayList<>();
        for (int[] interval : intervals) {
            // No overlap
            if (interval[1] <= left || interval[0] >= right) {
                newIntervals.add(interval);
            } else {
                // Overlap
                if (interval[0] < left) {
                    newIntervals.add(new int[]{interval[0], left});
                }
                if (interval[1] > right) {
                    newIntervals.add(new int[]{right, interval[1]});
                }
            }
        }
        intervals = newIntervals;
    }
}
```
### Algorithm
*   **Data Structure:** Use a `java.util.ArrayList<int[]>` to store the intervals, kept sorted by their start times.
*   **`addRange(left, right)`**:
    1.  Initialize an empty `newIntervals` list.
    2.  Iterate through the current `intervals` list.
    3.  For each existing interval, check for overlap with the new interval `[left, right)`.
    4.  If there is no overlap and the existing interval is before the new one, add it to `newIntervals`.
    5.  If there is no overlap and the existing interval is after the new one, first add the (potentially merged) new interval `[left, right)` if it hasn't been added yet, then add the existing interval.
    6.  If there is an overlap, merge the existing interval into the new one by updating `left = Math.min(left, interval[0])` and `right = Math.max(right, interval[1])`. Do not add anything to `newIntervals` yet.
    7.  After iterating through all intervals, add the final merged `[left, right)` interval to `newIntervals`.
    8.  Replace the original `intervals` list with `newIntervals`.
*   **`removeRange(left, right)`**:
    1.  Initialize an empty `newIntervals` list.
    2.  Iterate through the current `intervals` list.
    3.  For each existing interval, check for overlap with the removal interval `[left, right)`.
    4.  If there is no overlap, add the existing interval to `newIntervals`.
    5.  If there is an overlap, calculate the parts of the interval that remain. If `interval[0] < left`, add `[interval[0], left)` to `newIntervals`. If `interval[1] > right`, add `[right, interval[1])` to `newIntervals`.
    6.  Replace the original `intervals` list with `newIntervals`.
*   **`queryRange(left, right)`**:
    1.  Since the list is sorted, perform a binary search to find the interval with the largest start time that is less than or equal to `left`.
    2.  If such an interval `[start, end]` is found, check if its end `end` is greater than or equal to `right`.
    3.  Return `true` if the condition is met, otherwise `false`.

## Balanced Binary Search Tree (TreeMap)
This approach uses a `TreeMap` to store the disjoint intervals, mapping the start of each interval to its end. The `TreeMap` automatically keeps the intervals sorted by their start times and provides efficient methods (`floorEntry`, `subMap`, etc.) to find and manipulate intervals, leading to better performance than a simple list.
**Time:** `addRange`: O(k log N)
`removeRange`: O(k log N)
`queryRange`: O(log N)

Where N is the number of disjoint intervals and k is the number of intervals affected by the operation. This is significantly faster than the list-based approach for modifications. · **Space:** O(N), where N is the number of disjoint intervals.
**Pros:** Highly efficient operations. `queryRange` is `O(log N)`, and `addRange`/`removeRange` are also efficient with `O(k log N)` complexity, where `k` is small on average.; Scales well with a large number of intervals.; The use of `TreeMap` methods can lead to concise and elegant code for complex interval manipulations.
**Cons:** The implementation logic, especially for `addRange` and `removeRange`, is more complex than the list-based approach and requires careful handling of edge cases to ensure correctness.
### Explanation
We use a `java.util.TreeMap<Integer, Integer>` where the key is the interval's start and the value is its end. This structure is a balanced binary search tree, ensuring logarithmic time complexity for basic operations.

`addRange(left, right)`: We leverage `TreeMap` methods to find all existing intervals that overlap with or are adjacent to `[left, right)`. These intervals are then merged into a single large interval by taking the minimum of all start points and the maximum of all end points. We then remove all the old, now-merged intervals and insert the new, single, larger interval. `TreeMap`'s `subMap` view is very effective for removing a range of intervals at once.

`removeRange(left, right)`: This operation can be complex as it might split an existing interval. We handle this by first identifying any intervals that are partially overlapped by `[left, right)` at the boundaries. For an interval `[l, r)` that is partially overlapped, we trim it by adjusting its start or end, and if it's split in two, we add a new interval for the second part. For example, removing `[14, 16)` from `[10, 20)` results in `[10, 14)` and `[16, 20)`. After handling the boundaries, we remove all intervals that are fully contained within `[left, right)`.

`queryRange(left, right)`: This is the most efficient operation. We just need to find if there's a single tracked interval `[l, r)` that completely contains `[left, right)`. We use `map.floorEntry(left)` to find the interval that starts at or before `left`. If this interval exists and its end is at or after `right`, the range is covered. This is a single `O(log N)` lookup.

```java
class RangeModule {
    TreeMap<Integer, Integer> map;

    public RangeModule() {
        map = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        Map.Entry<Integer, Integer> start = map.floorEntry(left);
        if (start != null && start.getValue() >= left) {
            left = start.getKey();
        }
        Map.Entry<Integer, Integer> end = map.floorEntry(right);
        if (end != null && end.getValue() > right) {
            right = end.getValue();
        }
        map.subMap(left, true, right, false).clear();
        map.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);
        return entry != null && entry.getValue() >= right;
    }

    public void removeRange(int left, int right) {
        Map.Entry<Integer, Integer> start = map.floorEntry(left);
        if (start != null && start.getValue() > left) {
            map.put(start.getKey(), left);
        }
        Map.Entry<Integer, Integer> end = map.floorEntry(right);
        if (end != null && end.getValue() > right) {
            map.put(right, end.getValue());
        }
        map.subMap(left, true, right, false).clear();
    }
}
```
### Algorithm
*   **Data Structure:** Use a `java.util.TreeMap<Integer, Integer>` where keys are interval start points and values are interval end points.
*   **`addRange(left, right)`**:
    1.  Find any existing intervals that overlap or are adjacent to `[left, right)`. This can be done by checking intervals whose start is near `left` or `right`.
    2.  Merge `[left, right)` with all such overlapping/adjacent intervals by taking the minimum of all start points and the maximum of all end points.
    3.  Remove all the old intervals that were merged.
    4.  Insert the new, combined interval into the `TreeMap`.
    5.  This can be implemented cleanly by finding the new boundaries `[newLeft, newRight]`, removing all intervals within that range using `map.subMap(newLeft, newRight).clear()`, and then inserting the new interval `map.put(newLeft, newRight)`.
*   **`removeRange(left, right)`**:
    1.  Find an interval `[l, r)` that is partially overlapped by the start of the removal range (i.e., `l < left < r`). If found, trim it by updating its end to `left` (`map.put(l, left)`).
    2.  Find an interval `[l, r)` that is partially overlapped by the end of the removal range (i.e., `l < right < r`). If found, this may create a new interval `[right, r)`. The original interval might have already been trimmed in step 1.
    3.  A key insight is that a removal can split one interval into two. For an interval `[l, r)` that contains `[left, right)`, it becomes `[l, left)` and `[right, r)`.
    4.  Remove all intervals that are fully contained within `[left, right)` using `map.subMap(left, true, right, false).clear()`.
*   **`queryRange(left, right)`**:
    1.  Use `map.floorEntry(left)` to find the interval `[l, r)` with the largest start `l` such that `l <= left`.
    2.  If such an entry exists, check if its value `r` is greater than or equal to `right`.
    3.  Return `true` if `entry != null && entry.getValue() >= right`, otherwise `false`.

# Solutions
### Java

```java
class Node { Node left ; Node right ; int add ; boolean v ; } class SegmentTree { private Node root = new Node (); public SegmentTree () { } public void modify ( int left , int right , int v ) { modify ( left , right , v , 1 , ( int ) 1 e9 , root ); } public void modify ( int left , int right , int v , int l , int r , Node node ) { if ( l >= left && r <= right ) { node . v = v == 1 ; node . add = v ; return ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; if ( left <= mid ) { modify ( left , right , v , l , mid , node . left ); } if ( right > mid ) { modify ( left , right , v , mid + 1 , r , node . right ); } pushup ( node ); } public boolean query ( int left , int right ) { return query ( left , right , 1 , ( int ) 1 e9 , root ); } public boolean query ( int left , int right , int l , int r , Node node ) { if ( l >= left && r <= right ) { return node . v ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; boolean v = true ; if ( left <= mid ) { v = v && query ( left , right , l , mid , node . left ); } if ( right > mid ) { v = v && query ( left , right , mid + 1 , r , node . right ); } return v ; } public void pushup ( Node node ) { node . v = node . left != null && node . left . v && node . right != null && node . right . v ; } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node (); } if ( node . right == null ) { node . right = new Node (); } if ( node . add != 0 ) { node . left . add = node . add ; node . right . add = node . add ; node . left . v = node . add == 1 ; node . right . v = node . add == 1 ; node . add = 0 ; } } } class RangeModule { private SegmentTree tree = new SegmentTree (); public RangeModule () { } public void addRange ( int left , int right ) { tree . modify ( left , right - 1 , 1 ); } public boolean queryRange ( int left , int right ) { return tree . query ( left , right - 1 ); } public void removeRange ( int left , int right ) { tree . modify ( left , right - 1 , - 1 ); } } /** * 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); */
```

### CPP

```cpp
template < class T > class CachedObj { public: void * operator new ( size_t s ) { if ( ! head ) { T * a = new T [ SIZE ]; for ( size_t i = 0 ; i < SIZE ; ++ i ) add ( a + i ); } T * p = head ; head = head -> CachedObj < T >:: next ; return p ; } void operator delete ( void * p , size_t ) { if ( p ) add ( static_cast < T *> ( p )); } virtual ~ CachedObj () {} protected: T * next ; private: static T * head ; static const size_t SIZE ; static void add ( T * p ) { p -> CachedObj < T >:: next = head ; head = p ; } }; template < class T > T * CachedObj < T >:: head = 0 ; template < class T > const size_t CachedObj < T >:: SIZE = 10000 ; class Node : public CachedObj < Node > { public: Node * left ; Node * right ; int add ; bool v ; }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node (); } void modify ( int left , int right , int v ) { modify ( left , right , v , 1 , 1e9 , root ); } void modify ( int left , int right , int v , int l , int r , Node * node ) { if ( l >= left && r <= right ) { node -> v = v == 1 ; node -> add = v ; return ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; if ( left <= mid ) modify ( left , right , v , l , mid , node -> left ); if ( right > mid ) modify ( left , right , v , mid + 1 , r , node -> right ); pushup ( node ); } bool query ( int left , int right ) { return query ( left , right , 1 , 1e9 , root ); } bool query ( int left , int right , int l , int r , Node * node ) { if ( l >= left && r <= right ) return node -> v ; pushdown ( node ); int mid = ( l + r ) >> 1 ; bool v = true ; if ( left <= mid ) v = v && query ( left , right , l , mid , node -> left ); if ( right > mid ) v = v && query ( left , right , mid + 1 , r , node -> right ); return v ; } void pushup ( Node * node ) { node -> v = node -> left && node -> left -> v && node -> right && node -> right -> v ; } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node (); if ( ! node -> right ) node -> right = new Node (); if ( node -> add ) { node -> left -> add = node -> right -> add = node -> add ; node -> left -> v = node -> right -> v = node -> add == 1 ; node -> add = 0 ; } } }; class RangeModule { public: SegmentTree * tree ; RangeModule () { tree = new SegmentTree (); } void addRange ( int left , int right ) { tree -> modify ( left , right - 1 , 1 ); } bool queryRange ( int left , int right ) { return tree -> query ( left , right - 1 ); } void removeRange ( int left , int right ) { tree -> modify ( left , right - 1 , - 1 ); } }; /** * 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); */
```

### Python

```python
class Node : __slots__ = [ 'left' , 'right' , 'add' , 'v' ] def __init__ ( self ): self . left = None self . right = None self . add = 0 self . v = False class SegmentTree : __slots__ = [ 'root' ] def __init__ ( self ): self . root = Node () def modify ( self , left , right , v , l = 1 , r = int ( 1e9 ), node = None ): if node is None : node = self . root if l >= left and r <= right : if v == 1 : node . add = 1 node . v = True else : node . add = - 1 node . v = False return self . pushdown ( node ) mid = ( l + r ) >> 1 if left <= mid : self . modify ( left , right , v , l , mid , node . left ) if right > mid : self . modify ( left , right , v , mid + 1 , r , node . right ) self . pushup ( node ) def query ( self , left , right , l = 1 , r = int ( 1e9 ), node = None ): if node is None : node = self . root if l >= left and r <= right : return node . v self . pushdown ( node ) mid = ( l + r ) >> 1 v = True if left <= mid : v = v and self . query ( left , right , l , mid , node . left ) if right > mid : v = v and self . query ( left , right , mid + 1 , r , node . right ) return v def pushup ( self , node ): node . v = bool ( node . left and node . left . v and node . right and node . right . v ) def pushdown ( self , node ): if node . left is None : node . left = Node () if node . right is None : node . right = Node () if node . add : node . left . add = node . right . add = node . add node . left . v = node . add == 1 node . right . v = node . add == 1 node . add = 0 class RangeModule : def __init__ ( self ): self . tree = SegmentTree () def addRange ( self , left : int , right : int ) -> None : self . tree . modify ( left , right - 1 , 1 ) def queryRange ( self , left : int , right : int ) -> bool : return self . tree . query ( left , right - 1 ) def removeRange ( self , left : int , right : int ) -> None : self . tree . modify ( left , right - 1 , - 1 ) # 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)
```