## Algorithm

Problem Name: 715. Range Module

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.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`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const RangeModule = function() {
this.range = []
}

let index1 = this.range.length
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid] >= left) {
index1 = Math.min(index1, mid)
high = mid - 1
} else {
low = mid + 1
}
}

let index2 = -1
low = 0
high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid] <= right) {
index2 = Math.max(index2, mid)
low = mid + 1
} else {
high = mid - 1
}
}

if (index1 === this.range.length) {
this.range.push([left, right])
return
} else if (index2 === -1) {
this.range.unshift([left, right])
return
}
left = Math.min(left, this.range[index1])
right = Math.max(right, this.range[index2])
this.range.splice(index1, index2 - index1 + 1, [left, right])
}

RangeModule.prototype.queryRange = function(left, right) {
let index = -1
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid] <= left) {
index = Math.max(index, mid)
low = mid + 1
} else {
high = mid - 1
}
}
if (index === -1 || this.range[index] < right) {
return false
}
return true
}

RangeModule.prototype.removeRange = function(left, right) {
let index1 = this.range.length
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid] >= left) {
index1 = Math.min(index1, mid)
high = mid - 1
} else {
low = mid + 1
}
}

let index2 = -1
low = 0
high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid] <= right) {
index2 = Math.max(index2, mid)
low = mid + 1
} else {
high = mid - 1
}
}

if (index1 === this.range.length || index2 === -1) {
return
}

const newRange = []
if (left > this.range[index1]) {
newRange.push([this.range[index1], left])
}
if (right < this.range[index2]) {
newRange.push([right, this.range[index2]])
}
this.range.splice(index1, index2 - index1 + 1, ...newRange)
}
``````
Copy The Code &

Input

cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

cmd
[null, null, null, true, false, true]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
from bisect import bisect_left as bl, bisect_right as br

class RangeModule:

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

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, right):
i, j = br(self._X, left), bl(self._X, right)
return i == j and i%2 == 1

def removeRange(self, left, right):
i, j = bl(self._X, left), br(self._X, right)
self._X[i:j] = [left]*(i%2 == 1) + [right]*(j%2 == 1)
``````
Copy The Code &

Input

cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

cmd
[null, null, null, true, false, true]

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0715_RangeModule
{

public _0715_RangeModule()
{
list = new SortedList();
}

public void AddRange(int left, int right)
{
var leftIndex = GetIndex(left);
if (leftIndex >= 0) left = list.Keys[leftIndex];
else leftIndex = ~leftIndex;

var rightIndex = GetIndex(right);
if (rightIndex >= 0) right = list.Values[rightIndex];
else rightIndex = ~rightIndex - 1;

for (int i = leftIndex; i <= rightIndex; i++)
list.RemoveAt(leftIndex);

list[left] = right;
}

public bool QueryRange(int left, int right)
{
var leftIndex = GetIndex(left);
var rightIndex = GetIndex(right);
return leftIndex == rightIndex && leftIndex >= 0;
}

public void RemoveRange(int left, int right)
{
var leftIndex = GetIndex(left);
var rightIndex = GetIndex(right);

if (rightIndex >= 0)
list[right] = list.Values[rightIndex];
else
rightIndex = ~rightIndex - 1;

if (leftIndex >= 0)
{
list[list.Keys[leftIndex]] = left;
leftIndex++;
}
else
leftIndex = ~leftIndex;

for (int i = leftIndex; i <= rightIndex; i++)
list.RemoveAt(leftIndex);
}

private int GetIndex(int value)
{
var index = Array.BinarySearch(list.Keys.ToArray(), value);
if (index >= 0) return index;

index = ~index;
if (index > 0 && list.Values[index - 1] >= value)
return index - 1;
else
return ~index;
}
}

}
``````
Copy The Code &

Input

cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

cmd
[null, null, null, true, false, true]