Skip List estimate number of elements less than (or greater than) a value
Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach.  Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.).  Annotate each node with the size of the subtree under that node.  Then, make this data structure persistent.  This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely.  In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable.  Instead, updates essentially work by creating a new copy of the data structure.  Thus, each thread has its own copy of the tree.  The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree.  To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry).  Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.