c++ bst + queue
The idea is to have addElement and calculateMKAverage both in O(log m), although it still is O(m) in the worst case: a left only(or right only) childs tree.\n\n
The idea is to have addElement and calculateMKAverage both in O(log m), although it still is O(m) in the worst case: a left only(or right only) childs tree.\n\n```\nclass BST {\n    struct node {\n        int data;\n        node* left;\n        node* right;\n        int lCount;\n        int rCount;\n        int lsum;\n        int rsum;\n        int multiplicity;\n    };\n\n    node* insert(int x, node* t) {\n        if(t == NULL)\n        {\n            t = new node;\n            t->data = x;\n            t->lCount = 0;\n            t->rCount = 0;\n            t->lsum = 0;\n            t->rsum = 0;\n            t->multiplicity = 1;\n            t->left = t->right = NULL;\n        }\n        else if(x < t->data)\n        {\n            t->lCount++;\n            t->lsum += x;\n            t->left = insert(x, t->left);\n        }\n        else if(x > t->data)\n        {\n            t->rCount++;\n            t->rsum += x;\n            t->right = insert(x, t->right);\n        } else {\n            t->multiplicity++;\n        }\n        return t;\n    }\n\n    node* findMin(node* t) {\n        if(t == NULL)\n            return NULL;\n        else if(t->left == NULL)\n            return t;\n        else\n            return findMin(t->left);\n    }\n    \n    node* fullRemove(int x, node* t, int qt, int sr) {\n        node* temp;\n\n        // Element not found\n        if(t == NULL)\n            return NULL;\n\n        // Searching for element\n        else if(x < t->data) {\n            t->lCount-=qt;\n            t->lsum -= sr;\n            t->left = fullRemove(x, t->left, qt,sr);\n        }\n        else if(x > t->data) {\n            t->rCount-=qt;\n            t->rsum -= sr;\n            t->right = fullRemove(x, t->right, qt,sr);\n        }\n\n        // Element found\n        // With one or zero child\n        else\n        {\n            temp = t;\n            if(t->left == NULL)\n                t = t->right;\n            else if(t->right == NULL)\n                t = t->left;\n            delete temp;\n        }\n\n        return t;\n    }\n\n    node* remove(int x, node* t) {\n        node* temp;\n\n        // Element not found\n        if(t == NULL)\n            return NULL;\n\n        // Searching for element\n        else if(x < t->data) {\n            t->lCount--;\n            t->lsum -= x;\n            t->left = remove(x, t->left);\n        }\n        else if(x > t->data) {\n            t->rCount--;\n            t->rsum -= x;\n            t->right = remove(x, t->right);\n        }\n\n        // Element found\n        // repeated\n        else if(t->multiplicity > 1) {\n            t->multiplicity--;\n        }\n        // With 2 children\n        else if(t->left && t->right)\n        {\n            temp = findMin(t->right);\n            t->data = temp->data;\n            t->rCount-=temp->multiplicity;\n            t->rsum -= t->data*temp->multiplicity;\n            t->right = fullRemove(t->data, t->right,temp->multiplicity,t->data*temp->multiplicity);\n        }\n        // With one or zero child\n        else\n        {\n            temp = t;\n            if(t->left == NULL)\n                t = t->right;\n            else if(t->right == NULL)\n                t = t->left;\n            delete temp;\n        }\n        if(t == NULL)\n            return t;\n\n        return t;\n    }\n    \n    node* root;\n    void kSmallestSumRec(node *root, int k , int &temp_sum) {\n        if (root == NULL)\n            return ;\n\n        // if we fount k smallest element then break the function\n        if ((root->lCount + root->multiplicity) == k) {\n            temp_sum += root->data*root->multiplicity + root->lsum ;\n            return ;\n        }\n\n        else if (k > root->lCount)\n        {\n            // store sum of all element smaller than current root ;\n            temp_sum += root->lsum;\n            k -= root->lCount;\n            \n            if(root->multiplicity >= k) {\n                temp_sum += root->data*k;\n                return;\n            } else {\n                temp_sum += root->data*root->multiplicity;\n                k -= root->multiplicity;\n            }\n            \n            kSmallestSumRec(root->right , k , temp_sum);\n        }\n        else // call left sub-tree\n            kSmallestSumRec(root->left , k , temp_sum );\n    }\n    \n    void kGreatestSumRec(node *root, int k , int &temp_sum) {\n        if (root == NULL)\n            return ;\n\n        // if we fount k smallest element then break the function\n        if ((root->rCount + root->multiplicity) == k) {\n            temp_sum += root->data*root->multiplicity + root->rsum ;\n            return ;\n        }\n\n        else if (k > root->rCount)\n        {\n            temp_sum += root->rsum;\n            k -= root->rCount;\n            \n            if(root->multiplicity >= k) {\n                temp_sum += root->data*k;\n                return;\n            } else {\n                temp_sum += root->data*root->multiplicity;\n                k -= root->multiplicity;\n            }\n\n            kGreatestSumRec(root->left, k , temp_sum);\n        }\n        else // call left sub-tree\n            kGreatestSumRec(root->right, k , temp_sum);\n    }\n\n    public:\n    BST() {\n        root = NULL;\n    }\n\n    void insert(int x) {\n        root = insert(x, root);\n    }\n\n    void remove(int x) {\n        root = remove(x, root);\n    }\n\n    int kElementSum(int k) {\n        int sum = 0;\n        kSmallestSumRec(root, k, sum);\n        kGreatestSumRec(root, k, sum);\n        return sum;\n    }\n};\n\nclass MKAverage {\n    long long sum;\n    queue<int> elements;\n    int m;\n    int k;\n    BST* tree;\npublic:\n    MKAverage(int m, int k):m(m), k(k), sum(0) {\n        tree = new BST();\n    }\n    \n    void addElement(int num) {\n        if(elements.size() == m) {\n            sum = sum - elements.front();\n            tree->remove(elements.front());\n            elements.pop();\n        }\n\n        sum = sum + num;\n        tree->insert(num);\n        elements.push(num);\n    }\n    \n    int calculateMKAverage() {\n        if(elements.size() < m) return -1;\n        \n        return (sum - tree->kElementSum(k))/(m - 2*k);\n    }\n};\n```
['Binary Search Tree', 'Queue', 'C']