Practice Problem Set 7 (half-length)
Suppose that we wish to answer range median queries: that is, given a range [bottom,top] we wish to find the median of the keys within the range (the one in the middle position, rounding down if there are an even number of keys in the range). Describe how to do this using a constant number of ranking and unranking queries.
Consider an algorithm for the dynamic prefix sum problem that merely stores the array \(A\) itself, changes one array cell in each update (without performing any read operations), and answers queries by reading and adding all of the array cells up to the given cell i. For the sequence of eight update and eight query operations given in the lecture notes as an example of a difficult-to-solve sequence, what is the information transfer for this algorithm at each node of the binary tree of operations? What is the total number of read operations that it performs?