Range Module

hard design interval

Problem

addRange / queryRange / removeRange of half-open intervals.

Inputadd[10,20); query[10,14) → True; remove[14,16); query[10,14) → True

OutputTrue True

Maintain a normalized set of disjoint intervals.

input

from bisect import bisect_left, bisect_right, insort
class RangeModule:
    def __init__(self): self.r = []
    def addRange(self, l, r):
        i = bisect_left(self.r, l); j = bisect_right(self.r, r)
        merged = []
        if i % 2 == 1: i -= 1; merged.append(self.r[i])
        else: merged.append(l)
        if j % 2 == 1: merged.append(self.r[j]); j += 1
        else: merged.append(r)
        self.r[i:j] = merged
    def queryRange(self, l, r):
        i = bisect_right(self.r, l); j = bisect_left(self.r, r)
        return i == j and i % 2 == 1
    def removeRange(self, l, r):
        i = bisect_left(self.r, l); j = bisect_right(self.r, r)
        merged = []
        if i % 2 == 1: merged.append(l)
        if j % 2 == 1: merged.append(r)
        self.r[i:j] = merged

class RangeModule {
  constructor() { this.r = []; }
  bsl(x) { let lo = 0, hi = this.r.length; while (lo < hi) { const m = (lo + hi) >> 1; if (this.r[m] < x) lo = m + 1; else hi = m; } return lo; }
  bsr(x) { let lo = 0, hi = this.r.length; while (lo < hi) { const m = (lo + hi) >> 1; if (this.r[m] <= x) lo = m + 1; else hi = m; } return lo; }
  addRange(l, r) {
    let i = this.bsl(l), j = this.bsr(r); const m = [];
    if (i % 2 === 0) m.push(l); else { i--; m.push(this.r[i]); }
    if (j % 2 === 0) m.push(r); else { m.push(this.r[j]); j++; }
    this.r.splice(i, j - i, ...m);
  }
  queryRange(l, r) { const i = this.bsr(l), j = this.bsl(r); return i === j && i % 2 === 1; }
  removeRange(l, r) {
    const i = this.bsl(l), j = this.bsr(r); const m = [];
    if (i % 2 === 1) m.push(l);
    if (j % 2 === 1) m.push(r);
    this.r.splice(i, j - i, ...m);
  }
}

// Java implementation uses TreeMap for floor/ceiling ops on disjoint intervals.
class RangeModule {
    TreeMap ranges = new TreeMap<>();
    public void addRange(int l, int r) {
        Map.Entry lo = ranges.floorEntry(l), hi = ranges.floorEntry(r);
        if (lo != null && lo.getValue() >= l) l = lo.getKey();
        if (hi != null && hi.getValue() > r) r = hi.getValue();
        ranges.subMap(l, r).clear(); ranges.put(l, r);
    }
    public boolean queryRange(int l, int r) {
        Map.Entry e = ranges.floorEntry(l);
        return e != null && e.getValue() >= r;
    }
    public void removeRange(int l, int r) {
        Map.Entry lo = ranges.floorEntry(l), hi = ranges.lowerEntry(r);
        if (hi != null && hi.getValue() > r) ranges.put(r, hi.getValue());
        if (lo != null && lo.getValue() > l) ranges.put(lo.getKey(), l);
        ranges.subMap(l, r).clear();
    }
}

// C++ implementation uses std::map for ordered ops on disjoint intervals.
class RangeModule {
    map r;
public:
    void addRange(int l, int R) {
        auto it = r.upper_bound(l); if (it != r.begin()) { --it; if (it->second < l) ++it; }
        while (it != r.end() && it->first <= R) { l = min(l, it->first); R = max(R, it->second); it = r.erase(it); }
        r[l] = R;
    }
    bool queryRange(int l, int R) {
        auto it = r.upper_bound(l); if (it == r.begin()) return false;
        return (--it)->second >= R;
    }
    void removeRange(int l, int R) {
        auto it = r.upper_bound(l); if (it != r.begin()) { --it; if (it->second < l) ++it; }
        while (it != r.end() && it->first < R) {
            int s = it->first, e = it->second; it = r.erase(it);
            if (s < l) r[s] = l; if (e > R) r[R] = e;
        }
    }
};

Explanation

The core idea is to keep all the "tracked" intervals as a single sorted list of disjoint boundaries. The Python solution stores them flat: even positions are interval starts, odd positions are ends. Because they never overlap, this list stays in increasing order, and binary search can locate where any value belongs in O(log n).

A handy property falls out of this layout: a point is covered exactly when its insertion index in the list is odd (it sits between a start and its matching end). queryRange(l, r) uses this — it finds the positions of l and r and confirms they fall inside the same interval.

addRange finds where l and r slot in, then splices out everything between them, replacing it with the merged interval's new endpoints. The parity checks (i % 2 == 1) decide whether l or r already lands inside an existing interval, in which case we extend rather than add a boundary. removeRange works the mirror way, punching a hole.

Example: addRange(10, 20) makes the list [10, 20]. queryRange(10, 14) is True since both fall in [10,20). removeRange(14, 16) splits it into [10, 14, 16, 20], i.e. two intervals [10,14) and [16,20), and queryRange(10, 14) is still True.

Each operation is a binary search plus a splice over the k affected boundaries, so O(log n + k).

Time: O(log n + k) Space: O(n)