C++ Intuitive  Fenwick Tree Solution O(N * (logN)^2) w/explanation
First of all we only need to maintain a windows of size m at any point, so we maintain a queue for storing the numbers. \n\nFor MK Avg calculation, the whole se
First of all we only need to maintain a windows of size m at any point, so we maintain a queue for storing the numbers. \n\nFor MK Avg calculation, the whole search space of ```[1,10^5]``` is used for each testcase. \nI used 2 Fenwick Trees, for finding the sum of a given range in ```O(logN)``` time, the first tree is used.\n\nBut how to find the range?\nThere comes the second tree. We maintain a tree for getting the count of numbers upto a given number optimally. Then again, what we can do with a mere count? So, we do a search for the number from both the start and end to find the right value at which our wanted window for the answer starts and ends. Since we are searching in the space of ```[1,10^5]```, we can do a binary search for these 2 errands. \n\nSo if we know the boundary values, we can simply find the sum of all the elements, currently in our queue, which lie within these 2 values. \n\nOne last thing, when we update our queue, we update both our trees also, because we only want to search among the numbers which are currently in window of length ```m```.\n\nOne final optimization, if the starting and ending values occur more than once and we don\'t need all of them, for the given solution, I did a linear search. For that also a binary search can e done thus obtaining the mentioned complexity. That fragment of code is given in the comments.\n\n```\nclass FenwickTree\n{\npublic:\n\tvector<long> tree;\n\tlong sum=0;\n\tFenwickTree(int n)\n\t{\n\t\ttree.resize(n+1);\n\t}\n\tvoid update(int i,int val)\n\t{\n\t\twhile(i<tree.size())\n\t\t{\n\t\t\ttree[i]+=val;\n\t\t\ti+=i&(-i);\n\t\t}\n\t\tsum+=val;\n\t}\n\tint query(int i)\n\t{\n\t\tint ret=0;\n\t\twhile(i)\n\t\t{\n\t\t\tret+=tree[i];\n\t\t\ti=i&(i-1);\n\t\t}\n\t\treturn ret;\n\t}\n\tvoid append(int i)\n\t{\n\t\tint parent=tree.size();\n\t\tparent=parent&(parent-1);\n\t\tsum+=i;\n\t\ttree.push_back(sum-query(parent));\n\t}\n\tint binarySearch(int target)\n\t{\n\t\tint start=1,end=tree.size()-1;\n\t\twhile(start<end)\n\t\t{\n\t\t\tint q=start+(end-start)/2;\n\t\t\tint temp=query(q);\n\t\t\tif(temp>=target)\n\t\t\t\tend=q;\n\t\t\telse start=q+1;\n\t\t}\n\t\treturn end;\n\t}\n};\nclass MKAverage \n{\npublic:\n\tFenwickTree* sum=new FenwickTree(100000);\n\tFenwickTree* count = new FenwickTree(100000);\n\tint m,k;\n\tqueue<int> q;\n    MKAverage(int x, int y) \n    {\n        m=x;\n        k=y;\n    }\n    \n    void addElement(int num) \n    {\n        q.push(num);\n        if(q.size()>m)\n        {\n        \tint temp=q.front();\n        \tcount->update(temp,-1);\n        \tsum->update(temp,-temp);\n        \tq.pop();\n        }\n        count->update(num,1);\n        sum->update(num,num);\n    }\n    \n    int calculateMKAverage() \n    {\n        if(q.size()<m)\n        \treturn -1;\n        int temp=count->sum;\n        int first=count->binarySearch(k),last=count->binarySearch(temp-k);\n        int firstCount=count->query(first),lastCount=count->query(last);\n        int firstSum=sum->query(first),lastSum=sum->query(last);\n        while(firstCount-->k)\n        \tfirstSum-=first;\n        while(lastCount-->temp-k)\n        \tlastSum-=last;\n        return (lastSum-firstSum)/(m-2*k);\n    }\n};\n```
['C', 'Binary Tree']