[Python3] Fenwick tree
\n\nclass Fenwick: \n\n    def __init__(self, n: int):\n        self.nums = [0]*(n+1)\n\n    def sum(self, k: int) -> int: \n        k += 1\n        ans = 0\n  
\n```\nclass Fenwick: \n\n    def __init__(self, n: int):\n        self.nums = [0]*(n+1)\n\n    def sum(self, k: int) -> int: \n        k += 1\n        ans = 0\n        while k:\n            ans += self.nums[k]\n            k &= k-1 # unset last set bit \n        return ans\n\n    def add(self, k: int, x: int) -> None: \n        k += 1\n        while k < len(self.nums): \n            self.nums[k] += x\n            k += k & -k \n\n\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k \n        self.data = deque()\n        self.value = Fenwick(10**5+1)\n        self.index = Fenwick(10**5+1)\n\n    def addElement(self, num: int) -> None:\n        self.data.append(num)\n        self.value.add(num, num)\n        self.index.add(num, 1)\n        if len(self.data) > self.m: \n            num = self.data.popleft()\n            self.value.add(num, -num)\n            self.index.add(num, -1)\n\n    def _getindex(self, k): \n        lo, hi = 0, 10**5 + 1\n        while lo < hi: \n            mid = lo + hi >> 1\n            if self.index.sum(mid) < k: lo = mid + 1\n            else: hi = mid\n        return lo \n            \n    def calculateMKAverage(self) -> int:\n        if len(self.data) < self.m: return -1 \n        lo = self._getindex(self.k)\n        hi = self._getindex(self.m-self.k)\n        ans = self.value.sum(hi) - self.value.sum(lo)\n        ans += (self.index.sum(lo) - self.k) * lo\n        ans -= (self.index.sum(hi) - (self.m-self.k)) * hi\n        return ans // (self.m - 2*self.k)\n        \n\n\n# Your MKAverage object will be instantiated and called as such:\n# obj = MKAverage(m, k)\n# obj.addElement(num)\n# param_2 = obj.calculateMKAverage()\n```
['Python3']