1. In the lecture we saw a technique for representing a one-dimensional static array of numbers by an array of prefix sums, which allowed us to solve queries that asked for the sum of the numbers in a contiguous subarray in constant time, by subtracting two prefix sums. Does the same technique with prefix minima instead of prefix sums allow constant-time queries that ask for the minimum value in a contiguous subarray? Why or why not? 2. Suppose we wish to maintain a binary search tree using a rotation-based algorithm (such as a red-black tree or a splay tree) but we wish to augment the nodes of the tree so that each node stores its height (the number of edges on the longest path from the node to a leaf that descends from it). Suppose also that, as part of the tree balancing process, we perform a rotation of a node x and its left child y (so that after the rotation x becomes the right child of y). Give pseudocode for computing the updated height values after the rotation. You may assume that the children of node z are z.left and z.right, and that the height of node z is stored in z.height. 3. Suppose that we have a set of real numbers stored in an order-statistic tree (that is, a binary tree in which each node is augmented with its number of descendants), and that the tree supports the following two operations: rank(x): return the number of elements smaller than x in the tree unrank(i): return the element whose rank is the given integer i Based on these two operations, describe how to efficiently answer the following more complex operation: jump(x,i): return the element i steps later than x in the sorted order (Your method for answering the jump operation only needs to work correctly when it is given a value x that is already in the tree and is not among the last i elements of the tree -- if x is not in the tree, or if there is no element i steps later than it, you may choose arbitrarily what jump should do. You do not need to describe how to implement rank and unrank.)