[Solved]: Data structure for range-value-sum

Problem Detail: 

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.

Asked By : user21996

Answered By : govindpatel

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30809

3.2K people like this

 Download Related Notes/Documents