Yea, I think you basically do need one of these: https://en.wikipedia.org/wiki/Order_statistic_tree

They're somewhat obscure though.