Data Structure to Support Max Value of Keys Greater than Given Value

Question

I want to support two operations:

1. Insert a (key, value) pair into the data structure in $O(\log n)$ time. The key can be assumed to be a unique integer.
2. Given an integer query value $v$, I want to return the (key, value) pair $P$ such that the value of $P$ is as great as possible amongst all (key, value) pairs with key greater than $v$ in $O(\log n)$ time. (Return NULL if no key is greater than $v$.)

Can this be done? My motivation comes from the longest increasing subsequence problem, which we know can be solved in $O(n \log n)$ time, with $n$ denoting the length of the input array. If we had a data structure like the one I described above, then it would lend itself to another $O(n \log n)$ solution to this problem: Iterate through the array in reverse order, performing operation 2 with $v$ equal to the $array[i]$ (the current array element). If no key in the data structure is greater than $v$, insert $(array[i], 1)$. Else insert $(array[i], max\_val + 1)$, where $max\_val$ is the result of the query. The answer is just the element of maximum value after traversing the entire array.

And as a bonus, what if we want to support finding the maximum value amongst keys in a two-sided range (i.e. one where there is an upper and lower bound)?

Answer 1

Yes. Store the pairs in a self-balancing binary search tree, keyed on "key", with each pair stored in a leaf of the tree, with the pairs in sorted order by their key ("from left to right" as you walk over the leaves).

Augment the tree, as follows: each internal node in the tree stores the maximum value of "value", among all leaves under that node. Note that you can maintain and update these augmented values as you do every operation, with no increase in the asymptotic running time. (In particular, the max-value in any node is always the larger of the max-values of its two children.)

Every operation on this tree can be done in $O(\log n)$ time.

Now, suppose you're given a pair $P$. In $O(\log n)$ time, you can find the leaf where this pair lives in the tree (or where it would live). Next, follow the path from this leaf to the root of the tree. Look at the set of right-children of each node on the path to the root. The subtrees rooted at these right-children cover all pairs that have a larger "key" than $P$, and only those pairs. So, you can take the largest of the max-values in those right-children. The path to the root will have $O(\log n)$ length, so you can traverse it and check all the right-children in $O(\log n)$ time. Thus your second operation can also be done in $O(\log n)$ time.