I need ideas for designing a data structure that does insert, delete and getmean(a,b) all in
O(log n) time. getmean(a,b) is the arithmetic mean of all number x in [a,b)
My Thoughts -
Generally, insert and delete operations could be done in O(log n) time if we store data in
Balanced Search Trees like AVL Trees. But to solve getmean(a,b) in O(log n) time we need to store
some additional information. For calculating mean we could do the following:
recursively do an in-depth traversal. If the current element <a then we don't need to traverse
the left sub-tree. If current element > b then we don't need to traverse the right-subtree.
If the current element is between a and b then we include that element in our set.
But this approach needs some modification. For consider the case where all the elements in the
collection are in [a,b). Then this method will traverse all the items in the collection.
Resulting in O(n) operation.
I think you can get $O(\log n)$ by making every node store the number of nodes and the sum of all beneath it. Inserting/deleting one node changes $\log n$ nodes above it, and a tree-rotation at balancing time only requires recomputation of one nodes from its children (the other node just copy what was already there), so it doesn't hurt our $O(\log n)$ addition/deletion. Now to find mean you locate the smallest and largest node from $[a,b)$, find their closest common ancestor, and remove from the sum at that ancestor record at most $2\log n$ disjoint subtrees that doesn't appear in the reduced copy of the tree only featuring $[a,b)$ nodes, so $O(\log n)$ to get the sum and the number of elements, hence the mean.