Range Module — Segment Tree / SortedDict

Problem

Implement a range module that tracks which ranges are covered:

addRange(l, r) — mark [l,r) as tracked
removeRange(l, r) — unmark [l,r)
queryRange(l, r) — return if [l,r) is fully tracked

Approach — Sorted Disjoint Intervals

Maintain sorted list of disjoint intervals. For each add/remove:

Find all intervals overlapping with [l,r)
Merge or split as needed

Time: O(n) per operation worst, O(log n) amortized | Space: O(n)

Solutions

Python

from sortedcontainers import SortedList
class RangeModule:
    def __init__(self):
        self.ranges=SortedList(key=lambda x:x[0])
    def addRange(self, left, right):
        lo=self.ranges.bisect_left((left,))-1
        i=max(0,lo)
        while i<len(self.ranges) and self.ranges[i][0]<=right:
            l,r=self.ranges.pop(i)
            left=min(left,l); right=max(right,r)
        self.ranges.add((left,right))
    def removeRange(self, left, right):
        lo=self.ranges.bisect_left((left,))-1
        i=max(0,lo); new_ranges=[]
        while i<len(self.ranges) and self.ranges[i][0]<right:
            l,r=self.ranges.pop(i)
            if l<left: new_ranges.append((l,left))
            if r>right: new_ranges.append((right,r))
        for nr in new_ranges: self.ranges.add(nr)
    def queryRange(self, left, right):
        idx=self.ranges.bisect_right((left,))-1
        return idx>=0 and self.ranges[idx][0]<=left and self.ranges[idx][1]>=right

Complexity

Time: O(n) worst per operation | Space: O(n)