I want to support two operations:
- Insert a (key, value) pair into the data structure in $O(\log n)$ time. The key can be assumed to be a unique integer.
- 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)?