1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ I can't tell what your question is. "Thoughts?" is too vague -- we expect you to frame a precise, focused, technical question. "Ways to make more specific?" -- what do you mean? You are the one proposing the data structure. Are you unclear on what you are proposing? Are you asking us to check your solution to your exercise problem? Basically, please edit the question to be clearer about exactly what you are asking. (Incidentally, your justification for $O(\log n)$ time sounds pretty sketchy to me.) $\endgroup$
    – D.W. ♦
    Oct 11, 2014 at 7:18

1 Answer 1

Reset to default
0
$\begingroup$

use Binary Index tree, segment tree for the range-value-sum it is the easiest way to do so and for range-2-max use a linear search to keep track of two maximums.For range-2-max you can also use min-heap(this can help you to find range-N-max).

BinaryIndexTree(fenwick tree) has many online tutorials read them and see this visualizer for understanding it. http://visualgo.net/bit.html

Hope this clears or solve your problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.