heap | bst
heap with lazy update 700ms\n\npython\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.lh1, self
# heap with lazy update 700ms\n\n```python\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.lh1, self.rh1 = [(0, i) for i in range(m-k)], [(0, i) for i in range(m-k, m)]\n        self.lh2, self.rh2 = [(0, i) for i in range(k)], [(0, i) for i in range(k, m)]\n        for h in [self.lh1, self.rh1, self.lh2, self.rh2]:\n            heapq.heapify(h)\n        self.dq = deque([0 for i in range(m)])\n        self.s = 0\n        self.i = m-1\n\n    def addElement(self, v):\n        self.i += 1\n        l1 = self.add(self.lh1, self.rh1, v, self.i)\n        l2 = self.add(self.lh2, self.rh2, v, self.i)\n        self.dq.popleft()\n        self.dq.append(v)\n        self.s += l1 - l2\n        # print(\'add\', v)\n        # print(\'lh1\', self.lh1)\n        # print(\'rh1\', self.rh1)\n        # print(\'lh2\', self.lh2)\n        # print(\'rh2\', self.rh2)\n        # print(\'s\', self.s)\n\n    def add(self, lh, rh, v, i):\n        m = self.m\n        k = self.k\n        dq = self.dq\n        s = 0\n\n        prev = dq[0]\n        if v >= rh[0][0]: \n            # new v adds to rh\n            heapq.heappush(rh, (v, i))\n            if prev <= -lh[0][0]:\n                # old v rmvs from lh, move smallest from rh to lh for balancing\n                _v, _i = heapq.heappop(rh)\n                heapq.heappush(lh, (-_v, _i))\n                s += _v\n                s -= prev\n            else:\n                # old v rmvs from rh. do nothing\n                pass\n        else:\n            # new v adds to lh\n            heapq.heappush(lh, (-v, i))\n            s += v\n            if prev > -lh[0][0]:\n                # old v rmvs from rh, move biggest from lh to rh for balancing\n                _v, _i = heapq.heappop(lh)\n                heapq.heappush(rh, (-_v, _i))\n                s -= -_v\n            else:\n                # old v rmvs from lh\n                s -= prev\n\n        while lh and lh[0][1] <= i - m:\n            heapq.heappop(lh)\n        while rh and rh[0][1] <= i - m:\n            heapq.heappop(rh)\n        return s\n    \n    def calculateMKAverage(self):\n        if self.i < 2*self.m - 1:\n            return -1\n        return self.s // (self.m - self.k*2)\n```\n\n# balanced BST (sortedList), 950ms\n```python\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        from sortedcontainers import SortedList\n        self.sl = SortedList()\n        self.s = 0\n        self.l = 0\n        self.r = 0\n        self.dq = deque()\n        self.m = m\n        self.k = k\n\n    def addElement(self, v: int) -> None:\n        # O(logm)\n        dq = self.dq\n        sl = self.sl\n\n        if len(dq) == self.m:\n            prev = dq.popleft()\n            self.s -= prev\n\n            i = sl.index(prev)\n            if i >= self.m - self.k:\n                self.r -= prev\n                self.r += sl[-self.k-1]\n            if i <= self.k-1:\n                self.l -= prev\n                self.l += sl[self.k]\n            sl.remove(prev)\n\n        self.s += v\n        dq.append(v)\n        \n        sl.add(v)\n        i = sl.bisect_left(v)\n        if i >= len(sl) - self.k:\n            self.r += v\n            if len(sl) >= self.k+1:\n                self.r -= sl[-self.k-1]\n\n        i = sl.bisect_right(v) - 1\n        if i <= self.k - 1:\n            self.l += v\n            if len(sl) >= self.k+1:\n                self.l -= sl[self.k]\n\n    def calculateMKAverage(self) -> int:\n        # O(1)\n        if len(self.dq) < self.m:\n            return -1\n        v = self.s - self.l - self.r\n        n = self.m - self.k - self.k\n        v = v // n\n        return v\n```
['Binary Search Tree', 'Heap (Priority Queue)', 'Python3']