## Approach 1: Segment Tree

• Time:Constructor: O(1), addRange(left: int, right: int): O(\log 10^9), queryRange(left: int, right: int): O(\log 10^9), removeRange(left: int, right: int): O(\log 10^9)
• Space:O(n)

## C++

``````struct SegmentTreeNode {
int lo;
int hi;
bool tracked = false;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int lo, int hi, bool tracked, SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr)
: lo(lo), hi(hi), tracked(tracked), left(left), right(right) {}
~SegmentTreeNode() {
delete left;
delete right;
left = nullptr;
right = nullptr;
}
};

class SegmentTree {
public:
SegmentTree() : root(new SegmentTreeNode(0, 1e9, false)) {}

void addRange(int i, int j) {
update(root.get(), i, j, true);
}

bool queryRange(int i, int j) {
return query(root.get(), i, j);
}

void removeRange(int i, int j) {
update(root.get(), i, j, false);
}

private:
std::unique_ptr<SegmentTreeNode> root;

void update(SegmentTreeNode* root, int i, int j, bool tracked) {
if (root->lo == i && root->hi == j) {
root->tracked = tracked;
root->left = nullptr;
root->right = nullptr;
return;
}
const int mid = root->lo + (root->hi - root->lo) / 2;
if (!root->left) {
root->left = new SegmentTreeNode(root->lo, mid, root->tracked);
root->right = new SegmentTreeNode(mid + 1, root->hi, root->tracked);
}
if (j <= mid)
update(root->left, i, j, tracked);
else if (i > mid)
update(root->right, i, j, tracked);
else {
update(root->left, i, mid, tracked);
update(root->right, mid + 1, j, tracked);
}
root->tracked = root->left->tracked && root->right->tracked;
}

bool query(SegmentTreeNode* root, int i, int j) {
if (!root->left)
return root->tracked;
if (root->lo == i && root->hi == j)
return root->tracked;
const int mid = root->lo + (root->hi - root->lo) / 2;
if (j <= mid)
return query(root->left, i, j);
if (i > mid)
return query(root->right, i, j);
return query(root->left, i, mid) && query(root->right, mid + 1, j);
}
};

class RangeModule {
public:
void addRange(int left, int right) {
}

bool queryRange(int left, int right) {
return tree.queryRange(left, right - 1);
}

void removeRange(int left, int right) {
tree.removeRange(left, right - 1);
}

private:
SegmentTree tree;
};
``````

## Approach 2: Ordered Map

• Time:Constructor: O(1), addRange(left: int, right: int): O(k\log n), queryRange(left: int, right: int): O(\log n), removeRange(left: int, right: int): O(k\log n), where k is # of overlapping ranges
• Space:O(n)

## C++

``````class RangeModule {
public:
void addRange(int left, int right) {
const auto [l, r] = getOverlapRanges(left, right);
if (l == r) {            // no overlaps
ranges[left] = right;  // add a new range
return;
}

auto last = r;
const int newLeft = min(l->first, left);
const int newRight = max((--last)->second, right);
ranges.erase(l, r);
ranges[newLeft] = newRight;  // add a new range
}

bool queryRange(int left, int right) {
auto it = ranges.upper_bound(left);
return it != begin(ranges) && (--it)->second >= right;
}

void removeRange(int left, int right) {
const auto [l, r] = getOverlapRanges(left, right);
if (l == r)  // no overlaps
return;

auto last = r;
const int newLeft = min(l->first, left);
const int newRight = max((--last)->second, right);
ranges.erase(l, r);
// add new ranges if needed
if (newLeft < left)
ranges[newLeft] = left;
if (right < newRight)
ranges[right] = newRight;
}

private:
using IT = map<int, int>::iterator;
map<int, int> ranges;

pair<IT, IT> getOverlapRanges(int left, int right) {
// point to 1st element with second >= than left
IT l = ranges.upper_bound(left);
// point to 1st element with first > than right
IT r = ranges.upper_bound(right);
if (l != begin(ranges) && (--l)->second < left)
++l;
return {l, r};
}
};
``````

## JAVA

``````class RangeModule {
public void addRange(int left, int right) {
Integer l = ranges.floorKey(left);
Integer r = ranges.floorKey(right);

if (l != null && ranges.get(l) >= left)
left = l;
if (r != null && ranges.get(r) > right)
right = ranges.get(r);

ranges.subMap(left, right).clear();
ranges.put(left, right);
}

public boolean queryRange(int left, int right) {
Integer l = ranges.floorKey(left);
return l == null ? false : ranges.get(l) >= right;
}

public void removeRange(int left, int right) {
Integer l = ranges.floorKey(left);
Integer r = ranges.floorKey(right);

if (r != null && ranges.get(r) > right)
ranges.put(right, ranges.get(r));
if (l != null && ranges.get(l) > left)
ranges.put(l, left);

ranges.subMap(left, right).clear();
}

private TreeMap<Integer, Integer> ranges = new TreeMap<>();
}
``````

## Approach 3: Heuristic

• Time:Constructor: O(1), addRange(left: int, right: int): O(n), queryRange(left: int, right: int): O(\log n), removeRange(left: int, right: int): O(n)
• Space:O(n)

## C++

``````class RangeModule:
def __init__(self):
self.A = []

def addRange(self, left: int, right: int) -> None:
i = bisect_left(self.A, left)
j = bisect_right(self.A, right)
self.A[i:j] = [left] * (i % 2 == 0) + [right] * (j % 2 == 0)

def queryRange(self, left: int, right: int) -> bool:
i = bisect_right(self.A, left)
j = bisect_left(self.A, right)
return i == j and i % 2 == 1

def removeRange(self, left: int, right: int) -> None:
i = bisect_left(self.A, left)
j = bisect_right(self.A, right)
self.A[i:j] = [left] * (i % 2 == 1) + [right] * (j % 2 == 1)
``````