[Javascript] 2 Segment Trees + Divide and Conquer
\nThe main idea is to create two seperate segment trees. One will store the count of the elements up to a specific element. So for example if the elements 1,2, 
\nThe main idea is to create two seperate segment trees. One will store the count of the elements up to a specific element. So for example if the elements 1,2, 3, 3, 4, 4 are given then it ll look sth like\n\n0 1 2 3 4 \n**0 1 2 4 5** <=cumulative counts up to a specific element (think prefix sums [0,i] )\n\nThe other segment tree will store the sum of the given elements. So in the previous example:\n0 1 2 3 4 \n**0 1 3 9 17**  <=cumualtive sum of given elements\n\nWhat I intend to do is always maintain m values in those trees, namely the m last elements. \nIf I can achieve that, then the required MK average boils down to calculating the average of the inbetween  range of elements.\n\nLet us denote with S and E the start and the end of my required window after we removed the first and last K elements. \nIn order to find those two indices, we ll have to use Divide and Conquer on the segment tree queries of the first segment tree. The whole idea is creating the function seachPrefixIndex(x) that recursively finds the leftmost index where the prefix[0,i]>=x\n\n\n![image](https://assets.leetcode.com/users/images/1006dba3-a478-40f0-8b19-c6c442aa8ff7_1618320195.3242278.jpeg)\nSince we know that my window will begin after I removed the first k elements, S will start from the k+1-th element. But the thing is that a given prefix may not contain the value k+1 per se. That would mean that I have multiple occurences of a value. \nIn the first example, if I wanted to remove k=2 elements, then i\'d have to search for (k+1=3), but as you can see there is no such value inside the Index segment tree values. That\'s because we have two occurences of the element 3 and as such the prefix is 4 instead of 3. So we ll have to adjust the divide and conquer method to search for the leftmost occurence of any value>=k+1 . \nOnce we find said index we ll have to take the (last) prefix[0:index]-k elements. \nThe same idea goes for the E (end) index of my window. Once a new element is given, we roll the whole thing by removing the earliest( first) element that was given. \n\n```\n\nclass ArraySegTree{\n    // Array to perfrom operations on, range query operation, PointUpdate operation\n    constructor(A,op=(a,b)=>a+b,upOp=(a,b)=>a+b,opSentinel=0){\n        this.n=A.length,this.t=[...Array(4*this.n+1)],this.op=op,this.upOp=upOp,this.opSentinel=opSentinel\n        //root\'s idx =1\n        this.build(A,1,0,this.n-1)\n    }\n    left=x=>this.t[2*x];right=x=>this.t[2*x+1]\n    build(A,idx,left,right){\n        if(left==right)\n            return this.t[idx]=A[left]\n        let mid=(left+right)>>1\n        this.build(A,2*idx,left,mid) //go left\n        this.build(A,2*idx+1,mid+1,right) //go right\n        this.t[idx]=this.op(this.left(idx),this.right(idx)) //merge\n    }\n    //just specify l,r on actual queries\n    //Here queries use the actul indices of the starting array A, so rangeQuery(0,n-1) returns the whole array\n    rangeQuery=(l,r,tl=0,tr=this.n-1,idx=1)=>{\n        if(l>r)\n            return this.opSentinel\n        if(l===tl&&r===tr)\n            return this.t[idx]\n        let mid=(tl+tr)>>1\n        return this.op(\n                this.rangeQuery(l,Math.min(r,mid),tl,mid,idx*2),\n                this.rangeQuery(Math.max(l,mid+1),r,mid+1,tr,idx*2+1)\n        ) \n    }\n    //just specify arrIdx,newVal on actual pointUpdates\n    pointUpdate=(arrIdx,newVal,tl=0,tr=this.n-1,idx=1)=>{\n        if(tl==tr)\n            return this.t[idx]=this.upOp(this.t[idx],newVal)\n        let mid=(tl+tr)>>1\n        if(arrIdx<=mid)\n            this.pointUpdate(arrIdx,newVal,tl,mid,2*idx)\n        else\n            this.pointUpdate(arrIdx,newVal,mid+1,tr,2*idx+1)\n        this.t[idx]=this.op(this.left(idx),this.right(idx))\n    }\n    seachPrefixIndex=(x,start=0,end=this.n-1)=>{\n        let s=this.rangeQuery(start,end)\n        if(s<x)\n            return -1\n        if(start===end)\n            return start\n        let mid=start+end>>1,left=this.rangeQuery(start,mid)\n        if( left>=x)\n            return this.seachPrefixIndex(x,start,mid)\n        else\n            return this.seachPrefixIndex(x-left,mid+1,end)\n    }\n}\n\nvar MKAverage = function(m, k) {\n    this.A=[],this.m=m,this.k=k,this.div=m-2*k\n    this.S1=new ArraySegTree([...Array(1e5+2)].map(d=>0))//indices\n    this.S2=new ArraySegTree([...Array(1e5+2)].map(d=>0))//sums\n};\n\n/** \n * @param {number} num\n * @return {void}\n */\nMKAverage.prototype.addElement = function(num) {\n    this.A.push(num)\n    this.S1.pointUpdate(num,1)\n    this.S2.pointUpdate(num,num)\n    if(this.A.length>this.m){\n        let z=this.A.shift()\n        this.S1.pointUpdate(z,-1)\n        this.S2.pointUpdate(z,-z)\n    }\n};\n\n/**\n * @return {number}\n */\nMKAverage.prototype.calculateMKAverage = function() {\n    if(this.A.length<this.m)\n        return -1\n    \n    let S=this.S1.seachPrefixIndex(this.k+1),\n        count1=this.S1.rangeQuery(0,S),\n        take=(count1-this.k)*S\n    \n    let E=this.S1.seachPrefixIndex(this.m-this.k),\n        count2=this.S1.rangeQuery(0,E),\n        remove=(count2-this.m+this.k)*E\n    \n    let midSum=this.S2.rangeQuery(S+1,E)\n    return (take+midSum-remove)/this.div>>0\n};\n```
['Tree', 'JavaScript']