Rank operation in search tree, number of nodes between 2 values
Use an AVL tree $T$ that is augmented so that each vertex $v$ also stores the number of vertices in the subtree of $T$ rooted at $v$.
Given two vertices $u$ and $v$ of the tree you can find the number of values between $u$'s and $v$'s key by summing the sizes of at most $O(\log n)$ subtrees of $T$ dangling from the (unique) path from $u$ to $v$ in $T$.
These are exactly the highlighted trees/vertices in this answer, which also gives you a $O(\log n)$-time algorithm to find them.
The time complexities of insertions, deletions, and searches are asymptotically unaffected (i.e., they are in $O(\log n)$).