c++ BIT | 300 ms
I had similar idea just with @ye15. So I posted c++ version here\n\nclass MKAverage {\npublic:\n    int m, k;\n    deque<int> dq;\n    long sum[100003], cnt[100
I had similar idea just with @ye15. So I posted c++ version here\n```\nclass MKAverage {\npublic:\n    int m, k;\n    deque<int> dq;\n    long sum[100003], cnt[100003];\n    MKAverage(int m, int k) {\n        memset(sum, 0, sizeof(sum));\n        this->m = m, this->k = k;\n    }\n    void update(int num, int val) {\n        int u = val / num;\n        num += 1;\n        while (num < 100002) {\n            cnt[num] += u;\n            sum[num] += val;\n            num += num & -num;\n        }\n    }\n    long get(long BIT[],int x) {\n        long res = 0;\n        x += 1;\n        while (x) {\n            res += BIT[x];\n            x -= x & -x;\n        }\n        return res;\n    }\n    void addElement(int num) {\n        dq.push_back(num);\n        update(num, num);\n        if (dq.size() > m) {\n            update(dq.front(), -dq.front());\n            dq.pop_front();\n        }\n    }\n    int searchIndex(int kk) { // binary search\n        int low = 0, high = 1e5 + 1;\n        while (low < high) {\n            int mid = high + low >> 1;\n            if (get(cnt, mid) < kk) low = mid + 1;\n            else high = mid;\n        }\n        return low;\n    }\n    int calculateMKAverage() {\n        if (dq.size() < m)\n            return -1;\n        int low = searchIndex(k);\n        int high = searchIndex(m - k);\n        long ans = get(sum, high) - get(sum, low);\n        ans += (get(cnt, low) - k) * low;\n        ans -= (get(cnt, high) - (m - k)) * high;\n        return ans / (m - 2 * k);\n    }\n};\n```
['C', 'Binary Tree']