## 715. Range Module

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

• `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.
• `queryRange(int left, int right)` Returns true if and only if every real number in the interval `[left, right)` is currently being tracked.
• `removeRange(int left, int right)` Stops tracking every real number currently being tracked in the interval `[left, right)`.
• Example 1:

```addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)
```

Note:

• A half open interval `[left, right)` denotes all real numbers `left <= x < right`.
• `0 < left < right < 10^9` in all calls to `addRange, queryRange, removeRange`.
• The total number of calls to `addRange` in a single test case is at most `1000`.
• The total number of calls to `queryRange` in a single test case is at most `5000`.
• The total number of calls to `removeRange` in a single test case is at most `1000`.

• b'
\n\n

#### Approach #1: Maintain Sorted Disjoint Intervals [Accepted]

\n

Intuition

\n

Because `left, right < 10^9`, we need to deal with the coordinates abstractly. Let\'s maintain some sorted structure of disjoint intervals. These intervals will be closed (eg. we don\'t store `[[1, 2], [2, 3]]`; we would store `[[1, 3]]` instead.)

\n

In this article, we will go over Python and Java versions separately, as the data structures available to us that are relevant to the problem are substantially different.

\n

Algorithm (Python)

\n

We will maintain the structure as a list `self.ranges = []`.

\n

Adding a Range

\n

When we want to add a range, we first find the indices `i, j = self._bounds(left, right)` for which `self.ranges[i: j+1]` touches (in a closed sense - not halfopen) the given interval `[left, right]`. We can find this in log time by making steps of size 100, 10, then 1 in our linear search from both sides.

\n

Every interval touched by `[left, right]` will be replaced by the single interval `[min(left, self.ranges[i]), max(right, self.ranges[j])]`.

\n

Removing a Range

\n

Again, we use `i, j = self._bounds(...)` to only work in the relevant subset of `self.ranges` that is in the neighborhood of our given range `[left, right)`. For each interval `[x, y)` from `self.ranges[i:j+1]`, we may have some subset of that interval to the left and/or right of `[left, right)`. We replace our current interval `[x, y)` with those (up to 2) new intervals.

\n

Querying a Range

\n

As the intervals are sorted, we use binary search to find the single interval that could intersect `[left, right)`, then verify that it does.

\n

Python

\n
`class RangeModule(object):\n    def __init__(self):\n        self.ranges = []\n\n    def _bounds(self, left, right):\n        i, j = 0, len(self.ranges) - 1\n        for d in (100, 10, 1):\n            while i + d - 1 < len(self.ranges) and self.ranges[i+d-1] < left:\n                i += d\n            while j >= d - 1 and self.ranges[j-d+1] > right:\n                j -= d\n        return i, j\n\n    def addRange(self, left, right):\n        i, j = self._bounds(left, right)\n        if i <= j:\n            left = min(left, self.ranges[i])\n            right = max(right, self.ranges[j])\n        self.ranges[i:j+1] = [(left, right)]\n\n    def queryRange(self, left, right):\n        i = bisect.bisect_left(self.ranges, (left, float(\'inf\')))\n        if i: i -= 1\n        return (bool(self.ranges) and\n                self.ranges[i] <= left and\n                right <= self.ranges[i])\n\n    def removeRange(self, left, right):\n        i, j = self._bounds(left, right)\n        merge = []\n        for k in xrange(i, j+1):\n            if self.ranges[k] < left:\n                merge.append((self.ranges[k], left))\n            if right < self.ranges[k]:\n                merge.append((right, self.ranges[k]))\n        self.ranges[i:j+1] = merge\n`
\n
\n

Algorithm (Java)

\n

We will maintain the structure as a TreeSet `ranges = new TreeSet<Interval>();`. We introduce a new Comparable class `Interval` to represent our half-open intervals. They compare by right-most coordinate as later we will see that it simplifies our work. Also note that this ordering is consistent with equals, which is important when dealing with Sets.

\n

Adding and Removing a Range

\n

The basic structure of adding and removing a range is the same. First, we must iterate over the relevant subset of `ranges`. This is done using iterators so that we can `itr.remove` on the fly, and breaking when the intervals go too far to the right.

\n

The critical logic of `addRange` is simply to make `left, right` the smallest and largest seen coordinates. After, we add one giant interval representing the union of all intervals seen that touched `[left, right]`.

\n

The logic of `removeRange` is to remember in `todo` the intervals we wanted to replace the removed interval with. After, we can add them all back in.

\n

Querying a Range

\n

As the intervals are sorted, we search to find the single interval that could intersect `[left, right)`, then verify that it does. As the TreeSet uses a balanced (red-black) tree, this has logarithmic complexity.

\n

Java

\n
`class RangeModule {\n    TreeSet<Interval> ranges;\n    public RangeModule() {\n        ranges = new TreeSet();\n    }\n\n    public void addRange(int left, int right) {\n        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();\n        while (itr.hasNext()) {\n            Interval iv = itr.next();\n            if (right < iv.left) break;\n            left = Math.min(left, iv.left);\n            right = Math.max(right, iv.right);\n            itr.remove();\n        }\n        ranges.add(new Interval(left, right));\n    }\n\n    public boolean queryRange(int left, int right) {\n        Interval iv = ranges.higher(new Interval(0, left));\n        return (iv != null && iv.left <= left && right <= iv.right);\n    }\n\n    public void removeRange(int left, int right) {\n        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();\n        ArrayList<Interval> todo = new ArrayList();\n        while (itr.hasNext()) {\n            Interval iv = itr.next();\n            if (right < iv.left) break;\n            if (iv.left < left) todo.add(new Interval(iv.left, left));\n            if (right < iv.right) todo.add(new Interval(right, iv.right));\n            itr.remove();\n        }\n        for (Interval iv: todo) ranges.add(iv);\n    }\n}\n\nclass Interval implements Comparable<Interval>{\n    int left;\n    int right;\n\n    public Interval(int left, int right){\n        this.left = left;\n        this.right = right;\n    }\n\n    public int compareTo(Interval that){\n        if (this.right == that.right) return this.left - that.left;\n        return this.right - that.right;\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: Let be the number of elements in `ranges`. `addRange` and `removeRange` operations have complexity. `queryRange` has complexity. Because `addRange, removeRange` adds at most 1 interval at a time, you can bound these further. For example, if there are \n`addRange`, \n`removeRange`, and \n`queryRange` number of operations respectively, we can express our complexity as .

\n
• \n
• \n

Space Complexity: , the space used by `ranges`.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'