I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.
Any ideas along these lines would be much appreciated.
Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value