Problem statement

https://leetcode.com/problems/range-module/

Solution

Let us try to keep set of non-overlapping intervals in sorted order. For example, we have [0, 2], [4, 6], [8, 10], [12, 14] and we want to insert [5, 11]. What will happen after we try to add this interval: it will be [0, 2], [4, 11], [12, 14]. Perfect data structure to deal this updates is Sorted List in python: we need to look for the place of left end and for the place of right place. Also we need to check if we need to include numbers left and right: for this we can check parity of start and end. It works in similar way for removeRange as well. For queryRange, we just need to check that start is equal to end and that they are odd numbers.

Complexity

Imagine, that we make A add ranges, R remove and Q query ranges. Then we have complexity O((A + R + Q) * log(A + R)) Why? Because on each step number of ranges can be increased by at most 1, so we have no more than A + R of them, so each binary search we need at most O(log(A + R)) operations. Also at each iteration number of segments can either increased by 1, 0 or decreased. Sometimes it can be decreased a lot, like O(A + R), but we can say that decreament = increment + O(A + R), increment is O(A + R), so decrements is also O(A + R). So in the end we will do O(A + R) add and deletions from our sorted list, complexity of each of them is O(log(A + R)).

Code

from sortedcontainers import SortedList

class RangeModule:
    def __init__(self):
        self.ranges = SortedList()
        
    def rangeHelper(self, left, right, bit):
        start = SortedList.bisect_left(self.ranges, left)
        end = SortedList.bisect_right(self.ranges, right)
        for _ in range(end - start): self.ranges.pop(start)

        if start % 2 == bit: self.ranges.add(left)
        if end % 2 == bit: self.ranges.add(right)

    def addRange(self, left, right):
        self.rangeHelper(left, right, 0)

    def removeRange(self, left, right):
        self.rangeHelper(left, right, 1)
		
    def queryRange(self, left, right):
        start = SortedList.bisect_right(self.ranges, left)
        end = SortedList.bisect_left(self.ranges, right)
		
        return start == end and start % 2 == 1

Remark

See also similar Problem 0057 Insert Interval, which is subproblem of this one: addRange function. There is also Segment Tree solution, TBD.