[Java] Fenwick Tree + Binary Search, O(logN) for both addElement & calculateMKAverage
\n// Time complexity : O(logN)\n// Space complexity : O(N)\n// N is the possible max value in stream, which is 100000 based on the description\n\nclass MKAverag
```\n// Time complexity : O(logN)\n// Space complexity : O(N)\n// N is the possible max value in stream, which is 100000 based on the description\n\nclass MKAverage {\n    \n    private int LIMIT = 100000;\n    \n    int m, k;\n    long sum;\n    Queue<Integer> q;\n    BIT bit1, bit2;\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        sum = 0;\n        q = new LinkedList<>();\n        bit1 = new BIT(LIMIT + 1);\n        bit2 = new BIT(LIMIT + 1);\n    }\n    \n    public void addElement(int num) {\n        q.offer(num);\n        bit1.update(num, 1);\n        bit2.update(num, num);\n        sum += num;\n        \n        if (q.size() > m) {\n            int r = q.poll();\n            bit1.update(r, -1);\n            bit2.update(r, -r);\n            sum -= r;\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if (q.size() < m) return -1;\n        \n        long lSum = findKSmallest(),\n             rSum = findKLargest();\n\n        return (int)((sum - lSum -rSum) / (m - 2 * k));\n        \n    }\n    \n    private long rangQuery(BIT bit, int hig, int low) {\n        return bit.query(hig) - bit.query(low - 1);\n    }\n    \n    private long findKSmallest() {\n        int l = 1, r = LIMIT, number = -1;\n        while (l + 1 < r) {\n            int m = l + (r - l) / 2;\n            long count = rangQuery(bit1, m, 1);\n            if (count >= k) r = m;\n            else l = m;\n        }\n        \n        if (rangQuery(bit1, l, 1) >= k) number = l;\n        else number = r;\n        \n        long cnt = rangQuery(bit1, number, 1),\n             sum = rangQuery(bit2, number, 1);\n        \n        return removeMoreThanK(sum, cnt, number);\n    }\n    \n    private long findKLargest() {\n        int l = 1, r = LIMIT, number = -1;\n        while (l + 1 < r) {\n            int m = l + (r - l) / 2;\n            long count = rangQuery(bit1, LIMIT, m);\n            if (count >= k) l = m;\n            else r = m;\n        }\n        \n        if (rangQuery(bit1, LIMIT, r) >= k) number = r;\n        else number = l;\n        \n        long cnt = rangQuery(bit1, LIMIT, number),\n             sum = rangQuery(bit2, LIMIT, number);\n        \n        return removeMoreThanK(sum, cnt, number);\n    }\n    \n    private long removeMoreThanK(long sum, long cnt, int number) {\n        if (cnt > k) {\n            return sum - (cnt - k) * number;\n        }\n        return sum;\n    }\n    \n    class BIT {\n        long[] array;\n        \n        BIT(int size) {\n            array = new long[size];\n        }\n        \n        public void update(int ind, int v) {\n            while (ind < array.length) {\n                array[ind] += v;\n                ind += ind & -ind;\n            }\n        }\n        \n        public long query(int ind) {\n            long res = 0;\n            while (ind > 0) {\n                res += array[ind];\n                ind -= ind & -ind;\n            }\n            return res;\n        }\n    }\n}\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage obj = new MKAverage(m, k);\n * obj.addElement(num);\n * int param_2 = obj.calculateMKAverage();\n */\n```
[]