Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$.
Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but getting the $k$-th largest element costs $O(\log{N})$.
I can't think of any way to create a data structure with the best of both worlds, that is that we can get the $k$-th largest element in $O(1)$, and insertions and deletions cost only $O(\log{n})$, but I can't prove that it isn't possible.
So far, my idea for a proof basically revolves around it being impossible to have $O(1)$ accesses without an array. We can't have a tree or a linked list without the time complexity becoming dependant on the number of elements. Then, if an array is required, the only way to insert an element in less than $O(\log{n})$ time is to add it to the end or to the front (which is $O(1)$). But if we do this, we can't maintain the sorting of the list. So we need another data-structure which maps a given $k$ to its real index in the array in $O(1)$ and which supports insertions/deletions in $O(\log{n})$. The only difference between this inner data structure and the outer one is that the elements in the inner array will be each number from $0$ to $n$, but I don't think that matters and now I'm just back where I started!
What's the answer?
