Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations? 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
An array is the only thing that will get you consistent lookup in constant time.

Removal &amp; Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal