Leetcode: 715. Range Module

Problem Statement

The solution with Lazy Segment Tree has time complexity of \(O(n \log m)\) where \(m\) is the maximum value in the interval, and space complexity of \(O(n)\):

class RangeModule:
    def __init__(self, left=1, right=10**9, full=False):
        self.left = left
        self.mid = left + (right - left) // 2
        self.right = right
        self.left_child = self.right_child = None
        self.full = full

    def addRange(self, left: int, right: int) -> None:
        self._update(left, right - 1, True)

    def removeRange(self, left: int, right: int) -> None:
        self._update(left, right - 1, False)

    def queryRange(self, left: int, right: int) -> bool:
        return self._query(left, right - 1)

    def _query(self, left: int, right: int) -> bool:
        if self.right < left or right < self.left:
            return True

        self._extend()
        if self.full or left <= self.left <= self.right <= right:
            return self.full

        return self.left_child._query(left, right) and self.right_child._query(
            left, right
        )

    def _update(self, left: int, right: int, value: bool) -> None:
        if self.right < left or right < self.left:
            return
        if left <= self.left <= self.right <= right:
            self.left_child = None
            self.right_child = None
            self.full = value
            return
        self._extend()
        self.left_child._update(left, right, value)
        self.right_child._update(left, right, value)
        self.full = self.left_child.full and self.right_child.full

    def _extend(self) -> None:
        if self.left_child is None and self.left < self.right:
            m = self.left + (self.right - self.left) // 2
            self.left_child = RangeModule(self.left, m, self.full)
            self.right_child = RangeModule(m + 1, self.right, self.full)

    def _print(self, level=0):
        print(" " * level, self.left, self.right, self.full)
        if self.left_child:
            self.left_child._print(level + 1)
            self.right_child._print(level + 1)


# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

TODO Write solution using array of indexes

The idea is to represent intervals in an array where even number are start of intervals and odd indexes are end of intervals.

["RangeModule","addRange","removeRange","queryRange","queryRange","queryRange"]
[[],[10,20],[14,16],[10,14],[13,15],[16,17]]
["RangeModule","addRange","addRange","removeRange","queryRange","queryRange","removeRange","removeRange","removeRange","removeRange","removeRange","queryRange","removeRange","addRange","removeRange","addRange","queryRange","queryRange","addRange","addRange","queryRange","removeRange","queryRange","addRange","queryRange","removeRange","removeRange","addRange","addRange","removeRange","removeRange","removeRange","addRange","addRange","queryRange","queryRange","queryRange","queryRange","queryRange","removeRange","removeRange","queryRange","addRange","addRange","addRange","queryRange","addRange","addRange","removeRange","addRange","queryRange","removeRange","addRange","queryRange","addRange","addRange","addRange","queryRange","addRange","queryRange","removeRange","removeRange","removeRange","removeRange","queryRange","removeRange","queryRange","queryRange","removeRange","queryRange","addRange","addRange","queryRange","removeRange","removeRange","queryRange","addRange","removeRange","removeRange","addRange","addRange","addRange","queryRange","queryRange","addRange","queryRange","removeRange","queryRange","removeRange","addRange","queryRange"]
[[],[55,62],[1,29],[18,49],[6,98],[59,71],[40,45],[4,58],[57,69],[20,30],[1,40],[73,93],[32,93],[38,100],[50,64],[26,72],[8,74],[15,53],[44,85],[10,71],[54,70],[10,45],[30,66],[47,98],[1,7],[44,78],[31,49],[62,63],[49,88],[47,72],[8,50],[49,79],[31,47],[54,87],[77,78],[59,100],[8,9],[50,51],[67,93],[25,86],[8,92],[31,87],[90,95],[28,56],[10,42],[27,34],[75,81],[17,63],[78,90],[9,18],[51,74],[20,54],[35,72],[2,29],[28,41],[17,95],[73,75],[34,43],[57,96],[51,72],[21,67],[40,73],[14,26],[71,86],[34,41],[10,25],[27,68],[18,32],[30,31],[45,61],[64,66],[18,93],[13,21],[13,46],[56,99],[6,93],[25,36],[27,88],[82,83],[30,71],[31,73],[10,41],[71,72],[9,56],[22,76],[38,74],[2,77],[33,61],[74,75],[11,43],[27,75]]