Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
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