[Python] 4 heaps, one list, O(n log n), explained
The idea is similar to problem 480. Sliding Window Median, here we also have sliding window, but we need to find not median, but some other statistics: sum of s
The idea is similar to problem **480. Sliding Window Median**, here we also have sliding window, but we need to find not median, but some other statistics: sum of some middle elements in sorted window. Imagine for the purpose of example that `m = 7` and `k = 2`. Then we have widow of size `7`: `a1 < a2 < a3 < a4 < a5 < a6 < a7` and we need to evaluate the sum of `3` numbers `a3 + a4 + a5`. Let us solve two problems: evaluate `a1 + a2 + a3 + a4 + a5` and then substitute `a1 + a2`. How we are going to evaluate sum `a1 + a2` for example?\n\nThe idea is to keep `2` heaps: one for smallest `2` numbers in sliding window and another is for the `5` biggest numbers. We do it in very similar way as problem **480**, however we need to also evaluate sums. The trick is to use lazy deletion from heap, that is sometimes it happen, that there are some old elements in our window we need to be deleted later. If you know what is lazy deletion from heap, I think you got the idea, if not, please google it. The difficult part is how to update sum in heap as well, we need to do it carefully, because we have lazy updates, we need to make sure when we add or delete element, that it is element which will not be lazy update.\n\nFinally, we need to solve two separate problems: one for parts with sizes `2 vs 5` and another with sizes `5 vs 2`. Also I use trick where I fill heap with zeroes at first, so no need to check case when we do not have enough elements it parts.\n\n#### Complexity\nTime complexity is `O(n log n)`, where `n` is total number of calls of `addElement`. Space complexity is `O(n)`.\n\n```\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        self.m, self.k = m, k\n        self.arr = [0]*m\n        self.lh1, self.rh1 = self.heap_init(m, k)\n        self.lh2, self.rh2 = self.heap_init(m, m - k)\n        self.score = 0\n        \n    def heap_init(self, p1, p2):\n        h1 = [(0, i) for i in range(p1-p2, p1)]\n        h2 = [(0, i) for i in range(p1-p2)]\n        heapq.heapify(h1)\n        heapq.heapify(h2)\n        return (h1, h2)\n        \n    def update(self, lh, rh, m, k, num):\n        score, T = 0, len(self.arr)\n        if num > rh[0][0]:\n            heappush(rh, (num, T))        \n            if self.arr[T - m] <= rh[0][0]:\n                if rh[0][1] >= T - m: score += rh[0][0]\n                score -= self.arr[T - m]\n                heappush(lh, (-rh[0][0], rh[0][1]))\n                heappop(rh)\n        else:\n            heappush(lh, (-num, T))       \n            score += num\n            if self.arr[T - m] >= rh[0][0]: \n                heappush(rh, (-lh[0][0], lh[0][1]))\n                q = heappop(lh)\n                score += q[0]\n            else:\n                score -= self.arr[T - m]\n\n        while lh and lh[0][1] <= T - m: heappop(lh)  # lazy-deletion\n        while rh and rh[0][1] <= T - m: heappop(rh)  # lazy-deletion\n        return score\n        \n    def addElement(self, num):\n        t1 = self.update(self.lh1, self.rh1, self.m, self.k, num)\n        t2 = self.update(self.lh2, self.rh2, self.m, self.m - self.k, num)\n        self.arr.append(num)\n        self.score += (t2 - t1)\n    \n    def calculateMKAverage(self):\n        if len(self.arr) < 2*self.m: return -1\n        return self.score//(self.m - 2*self.k)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Heap (Priority Queue)']