[Python] Segment Tree - Annotated
If you are not familiar with segment trees, minutes 3:10 through 14:20 of this tutorial are very helpful:  \n\nhttps://www.youtube.com/watch?v=Tr-xEGoByFQ&t=156
If you are not familiar with segment trees, minutes 3:10 through 14:20 of this tutorial are very helpful:  \n\nhttps://www.youtube.com/watch?v=Tr-xEGoByFQ&t=1566s\n\nIf the video doesnt play, you can search for "Algorithms Live Segment Trees" or click on the link above.\n_____\n_____\nThe code below is an implementation of a segment tree where each node has an attribute node.count.  node.count counts the number of times each number occurs in the range ```[i, j]```.  node.val contains the range boundaries ```[i, j]```.  \n_____\n_____\n```python\nfrom collections import Counter\n\nclass Node(object):\n    \'\'\'\n    Node of the segment tree.  \n    \n    self.val = [i,j] where i and j are lower and upper bound indices in array (arr)\n    self.count = Counter(arr[i:j+1])  <-- keeps track of the frequency of each value in the range [i,j] inclusive\n    \'\'\'\n    def __init__(self,val):\n        self.val = val\n        self.count = None\n\nclass Segment_Tree(object):\n    def __init__(self, arr):\n        self.arr = arr\n        self.root = self.build(0,len(arr)-1)\n        \n    def build(self, i, j):\n        \'\'\'\n        constructs segment tree where each node has:\n        \n            1. a value of the index range [i,j] (inclusive) that it covers\n            2. a counter for how many times each number appears in the range [i,j]j\n            \n        *Note, self.root will look like:\n        \n            self.root.val = [0, len(arr) - 1]\n            self.root.count = Counter(arr)\n        \'\'\'\n        \n        if i == j:\n            node = Node([i,i])\n            node.count = Counter([self.arr[i]])\n            return node\n        \n        node = Node([i,j])\n        k = (i+j)>>1\n        node.left = self.build(i,k)\n        node.right = self.build(k+1,j)\n        \n        node.count = node.left.count + node.right.count\n        \n        return node\n        \n\n    def find_most_common(self, l, r, threshold):\n        \'\'\'\n        returns a tuple of (most common element, frequency) in the range l, r\n        where 0 <= l <= r < self.arr.length\n        \n        This is done as a subtraction process:\n        \n            1. res = self.root.count.copy()  <-- equivalent to Counter(arr)\n            2. subtract values from res for ranges that are not included in l, r\n            3. During this process, if the most frequent value in res ever occurs\n               less than treshold times, then trigger the sentinel to quit out\n            4. If a range [i,j] on the tree is completely contained within [l,r] inclusive\n               then do not subtract the values in A[i:j+1] from the result\n        \'\'\'\n        \n        res = self.root.count.copy()\n        \n        sentinel = False #3\n        \n        def helper(node):\n            nonlocal res, l, r, sentinel, threshold\n            \n            if sentinel: return None #3\n            \n            if (not res) or max(res.values()) < threshold: #3\n                #there is no solution so set res = {} and escape recursive function\n                sentinel = True\n                res = {} \n                return None\n\n            i, j = node.val\n            if (j < l) or (i > r): #2\n                #this node has only values that are OUTSIDE of [left,right] so subtract them from res\n                res -= node.count\n                return None\n            \n            if (l <= i) and (j <= r): #4\n                #this node has only values that are INSIDE of [left,right] so keep the values\n                return None\n\n            helper(node.left)\n            helper(node.right)\n        \n        helper(self.root)\n        most_common = max(res, key = lambda k: res[k]) if res else (-1,-1)\n        \n        return (most_common, res[most_common]) if res else most_common\n        \n\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.tree = Segment_Tree(arr)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        #Find the value (val) that occurs the most frequently in range [left,right]\n        val, freq = self.tree.find_most_common(left, right, threshold)\n        return val if freq >= threshold else -1\n```
[]