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 &lt;= x &lt; 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).


&nbsp;
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)


&nbsp;
Constraints:


	1 &lt;= left &lt; right &lt;= 109
	At most 104 calls will be made to addRange, queryRange, and removeRange.


from bisect import bisect_left as bl, bisect_right as br
class RangeModule:

    def __init__(self):
        self._X = []

    def addRange(self, left: int, right: int) -> None:
        # Main Logic 
        #   If idx(left) or idx(right) is odd, it's in a interval. So don't add it. 
        #   If idx(left) or idx(right) is even, it's not in any interval. So add it as new interval 
        #   Slice array[idx(left) : idx(right)]
        #       1) both odd: Nothing is added. Merge all middle intervals. 
        #       2) both even: Add new intervals. Merge all middle intervals
        #       3) idx(left) is even: update start point of next interval with left
        #       4) idx(right) is even: update end point of previous interval with right
        # Bisect_left vs. Bisect_right
        #   left need to proceed all interval closing at left, so use Bisect_left
        #   right need to go after all interval openning at right, so use Bisect_right
        i, j = bl(self._X, left), br(self._X, right)
        self._X[i : j] = [left] * (i % 2 == 0) + [right] * (j % 2 == 0)
        

    def queryRange(self, left: int, right: int) -> bool:
        # Main logic 
        #   If idx of left/right is odd, it's in a interval. Else it's not. 
        #   If idx of left&right is the same, they're in the same interval
        # Bisect_left vs. Bisect_right
        #   [start, end). Start is included. End is not. 
        #   so use bisect_right for left 
        #   so use bisect_left for right 
        i, j = br(self._X, left), bl(self._X, right)
        return i == j and i % 2 == 1
        

    def removeRange(self, left: int, right: int) -> None:
        # Main Logic 
        #   If idx(left) is odd, the interval that contains left need to change end point to left 
        #   If idx(right) is odd, the interval that contains right need to change start point to right
        #   Else, everything from idx(left) to idx(right) is removed. Nothing is changed. 
        # Bisect_left vs. Bisect_right
        #   Same as addRange
        i, j = bl(self._X, left), br(self._X, right)
        self._X[i : j] = [left] * (i % 2 == 1) + [right] * (j % 2 == 1)
class RangeModule {
    TreeMap<Integer, Integer> map;

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

    public void addRange(int left, int right) {
        // assume the given range [left, right), we want to find [l1, r1) and [l2, r2) such that l1 is the floor key of left, l2 is the floor key of right. Like this:
        // [left, right)
        // [l1, r1) [l2, r2)
        // Note: l2 could be the same as l1, so they are either both null or both non-null
        Integer l1 = map.floorKey(left);
        Integer l2 = map.floorKey(right);

        // try to visualize each case, and what to do based on r1
        if (l1 == null && l2 == null) {
            map.put(left, right);
        }
        else if (l1 != null && map.get(l1) >= left) {
            map.put(l1, Math.max(right, map.get(l2))); // r2 will always be greater than r1, so no need to check r1
        }
        else {
            map.put(left, Math.max(right, map.get(l2)));
        }

        // we don't want to remove the range starts at left, so left should be exclusive.
        // but we want to remove the one starts at right, so right should be inclusive.
        map.subMap(left, false, right, true).clear();
    }

    public boolean queryRange(int left, int right) {
        Integer l = map.floorKey(left);
        if (l != null && map.get(l) >= right) {
            return true;
        }
        return false;
    }

    public void removeRange(int left, int right) {
        Integer l1 = map.lowerKey(left); // I used lowerKey here, since we don't care about the range starting at left, as it should be removed
        Integer l2 = map.lowerKey(right); // same, we don't care about the range starting at right

        // do this first, in case l1 == l2, the later one will change r1(or r2 in this case)
        if (l2 != null && map.get(l2) > right) {
            map.put(right, map.get(l2));
        }

        if (l1 != null && map.get(l1) > left) {
            map.put(l1, left);
        }

        // range that starts at left should be removed, so left is inclusive
        // range that starts at right should be kept, so right is exclusive
        map.subMap(left, true, right, false).clear();
    }
}
/*
    https://leetcode.com/problems/range-module/

    Idea is to use a height balanced tree to save the intervals. Intervals are kept
    according to the start point.
    We search for the position where the given range can lie, then check the previous if it overlaps
    and keep iterating forward while the intervals are overlapping.

    QueryRange:
    We first find the range of values in [left, right). Then for each of the overlapping intervals,
    we subtract the common range. Finally if the entire range is covered, then the range will become zero.
*/
class RangeModule {
private:
    struct Interval {
        const bool operator<(const Interval& b) const {
            // Important to implement for == case, otherwise intervals
            // with same start won't exist
            // return start < b.start || (start == b.start && end < b.end);

            // This is the best way to compare since tuple already have ordering implemented for
            // fields
            return tie(start, end) < tie(b.start, b.end);
        }

        int start = -1, end = -1;
        Interval(int start, int end): start(start), end(end) {};
    };

    set<Interval> intervals;
public:
    RangeModule() {

    }

    // TC: Searching O(logn) + O(n) Merging, worst case when current interval covers all, insertion would take O(1)
    // SC: O(1)
    void addRange(int left, int right) {
        Interval interval(left, right);
        // Find the position where interval should lie st the next interval's
        // start >= left
        auto it = intervals.lower_bound(interval);

        // check if previous overlaps, move the iterator backwards
        if(!intervals.empty() && it != intervals.begin() && prev(it)->end >= interval.start) {
            --it;
            interval.start = min(it->start, interval.start);
        }

        // merge while intervals overlap
        while(it != intervals.end() && it->start <= interval.end) {
            interval.end = max(it->end, interval.end);
            intervals.erase(it++);
        }
        intervals.insert(interval);
    }

    // TC: Searching O(logn) + O(n) Merging, worst case when current interval covers all
    // SC: O(1)
    bool queryRange(int left, int right) {
        Interval interval(left, right);
        // Range of numbers that needs to be checked
        int range = right - left;
        // Find the position where interval should lie st the next interval's
        // start >= left
        auto it = intervals.lower_bound(interval);

        // check if previous interval overlaps the range, previous only
        // covers iff the open end > start of current. [prev.start, prev.end) [left, right)
        if(!intervals.empty() && it != intervals.begin() && prev(it)->end > interval.start) {
            // remove the common portion
            int common = min(interval.end, prev(it)->end) - interval.start;
            range -= common;
        }
        // for all the following overlapping intervals, remove the common portion
        while(it != intervals.end() && it->start <= interval.end) {
            int common = min(interval.end, it->end) - it->start;
            range -= common;
            ++it;
        }
        // Check if the entire range was covered or not
        return range == 0;
    }

    // TC: Searching O(logn) + O(n) Merging, worst case when current interval covers all
    // SC: O(1)
    void removeRange(int left, int right) {
        Interval interval(left, right);
        // Find the position where interval should lie st the next interval's
        // start >= left
        auto it = intervals.lower_bound(interval);

        // check if previous overlaps, then move the iterator position backwards
        if(!intervals.empty() && it != intervals.begin() && prev(it)->end > interval.start)
            --it;

        // For each of the overlapping intervals, remove the common portions
        while(it != intervals.end() && it->start < interval.end) {
            // Start and End of common portion
            int common_start = max(interval.start, it->start);
            int common_end = min(interval.end, it->end);

            // only a section of interval overlaps, remove that part
            // an overlapping interval might have to be broken into two non-overlapping parts
            // Eg [---------------------) Bigger interval
            // [--------) Ongoing interval
            // [------) [-----) Original interval broken into left and right parts

            // check if there is some range left on the left side
            if(it->start < common_start)
                intervals.insert(Interval(it->start, common_start));

            // check if there is some range left on the right side
            if(it->end > common_end)
                intervals.insert(Interval(common_end, it->end));

            // Remove the original interval
            intervals.erase(it++);
        }
    }
};

/**
 * 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);
 */
var RangeModule = function() {
    this.ranges = []
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {void}
 */
//Time: O(logN)
RangeModule.prototype.addRange = function(left, right) {
    const lIdx = this.findIndex(left), rIdx = this.findIndex(-right)
    if (lIdx === this.ranges.length) {
        this.ranges.push(left)
        this.ranges.push(-right)
    } else if (this.ranges[lIdx] < 0 && (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)) {
        this.ranges.splice(lIdx, rIdx - lIdx, -right)
    } else if (this.ranges[lIdx] < 0 && this.ranges[rIdx] < 0) {
        this.ranges.splice(lIdx, rIdx - lIdx)
    } else if (this.ranges[lIdx] > 0 && (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)) {
        this.ranges.splice(lIdx, rIdx - lIdx, left, -right)
    } else if (this.ranges[lIdx] > 0 && this.ranges[rIdx] < 0) {
        this.ranges.splice(lIdx, rIdx - lIdx, left)   
    }
    return null
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {boolean}
 */
//Time: O(logN)
RangeModule.prototype.queryRange = function(left, right) {
    const lIdx = this.findIndex(left), rIdx = this.findIndex(-right)
    if (lIdx === this.ranges.length) return false
    if (lIdx + 2 < rIdx) return false
    if (lIdx === rIdx) {
        return this.ranges[lIdx] < 0
    } else if (lIdx + 1 === rIdx) {
        return this.ranges[lIdx] === left || this.ranges[lIdx] === -right
    } {
        return this.ranges[lIdx] === left && Math.abs(this.ranges[lIdx + 1]) === right
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {void}
 */
//Time: O(logN)
RangeModule.prototype.removeRange = function(left, right) {
    let lIdx = this.findIndex(left), rIdx = this.findIndex(-right)
    if (lIdx === this.ranges.length) return null
    if (this.ranges[lIdx] < 0 && (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)) {
        this.ranges.splice(lIdx, rIdx - lIdx, -left)
    } else if (this.ranges[lIdx] < 0 && this.ranges[rIdx] < 0) {
        this.ranges.splice(lIdx, rIdx - lIdx, -left, right)
    } else if (this.ranges[lIdx] > 0 && (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)) {
        this.ranges.splice(lIdx, rIdx - lIdx)
    } else if (this.ranges[lIdx] > 0 && this.ranges[rIdx] < 0) {
        this.ranges.splice(lIdx, rIdx - lIdx, right)   
    }
    // console.log(this.ranges)
    return null
};

RangeModule.prototype.findIndex = function(number) {
    let l = 0, r = this.ranges.length
    while(l < r) {
        const m = l + ((r - l) >> 1)
        if (Math.abs(this.ranges[m]) > Math.abs(number)) {
            r = m
        } else if (Math.abs(this.ranges[m]) < Math.abs(number)) {
            l = m + 1
        } else {
            if (number < 0) {
                l = m + 1
            } else {
                r = m
            }
        }
    }
    return l
}

/** 
 * 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)
 */
Range Module