I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure.
Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of values of all elements whose keys are in the range of [xl,xr], where xl and xr are real numbers and xl ≤ xr
Range-2-max values reports the largest value and the second largest.
Approach: This is my take on it so far, to use a single balanced binary search tree that is sorted by its keys. The augmented fields would be the value (of the key-value pair), subtree min and max keys, sum of the subtree, and the 1st and 2nd maximum of its subtree. The sum and 1st and 2nd max are of the values, not keys since the values don't have to be ordered in this case. For range-value-sum the recursion is to pretty much keep track of the 1st and 2nd max values that are within the range. Finally, you return the top 2 in each recursive step, excluding unnecessary values.
Thoughts? Ways to make more specific? For the time analysis, I'm relying O(logn) due to it being a binary search tree and its height.