[Java] Fenwick Tree + BinarySearch
Idea : \n1. We can have a queue to maintain m elements\n2. Use two Fenwick tree, 1 for count and 1 for prefix sum\n3. Do 2 times binary search for the first k e
Idea : \n1. We can have a queue to maintain m elements\n2. Use two Fenwick tree, 1 for count and 1 for prefix sum\n3. Do 2 times binary search for the first k elements and the last k elements by using the count from our first fenwick tree\n4. We can get the sum by subtrating the sum of first k elements and sum of last k element by using our second fenwick tree\n\n```\nclass MKAverage {\n    Queue<Integer>q=new LinkedList<>();\n    int m,k;\n    FenWick fen1;\n    FenWick fen2;\n    int cnt[]=new int[100010];\n    long sum=0;\n    public MKAverage(int m, int k) {\n        this.m=m;\n        this.k=k;\n        long A[]=new long[100010];\n        long B[]=new long[100010];\n        fen1=new FenWick(A);\n        fen2=new FenWick(B);\n    }\n    \n    public void addElement(int num) {\n        q.add(num);\n        sum+=num;\n        fen1.update(num,1);\n        fen2.update(num,num);\n        cnt[num]++;\n    }\n    \n    public int calculateMKAverage() {\n        if(q.size()<m)return -1;\n        while(q.size()>m){\n            int peek=q.poll();\n            cnt[peek]--;\n            sum-=peek;\n            fen1.update(peek,-1);\n            fen2.update(peek,-peek);\n        }\n        \n        \n        \n        int l=0,r=cnt.length-1;\n        int pos1=-1,pos2=-1;\n        while(l<=r){//binary search for the first k (there may be duplicated)\n            int mid=l+(r-l)/2;\n            long count=fen1.sumRange(0,mid);\n            if(count>=k){\n                pos1=mid;\n                r=mid-1;\n            }\n            else{\n                l=mid+1;\n            }\n        }\n        \n        \n        \n        l=0;r=cnt.length-1;\n        while(l<=r){//binary search for the last k (there may be duplicated)\n            int mid=l+(r-l)/2;\n            long count=fen1.sumRange(mid,cnt.length-1);\n            if(count>=k){\n                pos2=mid;\n                l=mid+1;\n            }\n            else{\n                r=mid-1;\n            }\n        }\n        \n        \n        \n        long sum1=fen2.sumRange(0,pos1);\n        long sum2=fen2.sumRange(pos2,cnt.length-1);\n        long cnt1=fen1.sumRange(0,pos1);\n        long cnt2=fen1.sumRange(pos2,cnt.length-1);\n        \n        if(cnt1>k){\n            sum1-=(pos1*(cnt1-k));\n        }\n        if(cnt2>k){\n            sum2-=(pos2*(cnt2-k));\n        }\n        long remain=sum-sum1-sum2;\n        return (int)(remain/(m-2*k));\n    }\n}\n\nclass FenWick {\n    long tree[];//1-index based\n    long A[];\n    long arr[];\n    public FenWick(long[] A) {\n        this.A=A;\n        arr=new long[A.length];\n        tree=new long[A.length+1];\n    }\n    \n    public void update(int i, int val) {\n        arr[i]+=val;\n        i++;\n        while(i<tree.length){\n            tree[i]+=val;\n            i+=(i&-i);\n        }\n    }\n    \n    public long sumRange(int i, int j) {\n        return pre(j+1)-pre(i);\n    }\n    \n    public long pre(int i){\n        long sum=0;\n        while(i>0){\n            sum+=tree[i];\n            i-=(i&-i);\n        }\n        return sum;\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\n/*\n                             ;\\\n                            |\' \\\n         _                  ; : ;\n        / `-.              /: : |\n       |  ,-.`-.          ,\': : |\n       \\  :  `. `.       ,\'-. : |\n        \\ ;    ;  `-.__,\'    `-.|\n         \\ ;   ;  :::  ,::\'`:.  `.\n          \\ `-. :  `    :.    `.  \\\n           \\   \\    ,   ;   ,:    (\\\n            \\   :., :.    ,\'o)): ` `-.\n           ,/,\' ;\' ,::"\'`.`---\'   `.  `-._\n         ,/  :  ; \'"      `;\'          ,--`.\n        ;/   :; ;             ,:\'     (   ,:)\n          ,.,:.    ; ,:.,  ,-._ `.     \\""\'/\n          \'::\'     `:\'`  ,\'(  \\`._____.-\'"\'\n             ;,   ;  `.  `. `._`-.  \\\\\n             ;:.  ;:       `-._`-.\\  \\`.\n              \'`:. :        |\' `. `\\  ) \\\n      -hrr-      ` ;:       |    `--\\__,\'\n                   \'`      ,\'\n                        ,-\'\n\n\n                      free bug dog\n*/\n```
[]