code: def interval_tree(intervals):
      
      if intervals == []:
          return None
      center = intervals[len(intervals) // 2][0]
      L = []
      R = []
      C = []
      for I in intervals:
          if I[1] <= center:
              L.append(I)
          elif center < I[0]:
              R.append(I)
          else:
              C.append(I)
      by_low = sorted((I[0], I) for I in C)
      by_high = sorted((I[1], I) for I in C)
      IL = interval_tree(L)
      IR = interval_tree(R)
      return _Node(center, by_low, by_high, IL, IR)
docs: Construct an interval tree
  
      :param intervals: list of half-open intervals
                        encoded as value pairs *[left, right)*
      :assumes: intervals are lexicographically ordered
                ``>>> assert intervals == sorted(intervals)``
      :returns: the root of the interval tree
      :complexity: :math:`O(n)`