No idea if this is better off on MathOverflow.
A dynamic binary search tree (I assume that it can keep the tree strictly balanced, e.g. red-black, also the BST shall have n keys and each key shall be queried exactly once) can take minimum O(n) for a "good" instance (e.g. a sorted query) or maximum O(n log n) for a "bad" instance (e.g. a bit-reversal sequence).
If this is easier for you, this is an almost equal geometric setting, courtesy by Demaine: Draw n points in the plane (no equal x or y coordinates!). For each pair of points, draw the axis parallel rectangle with these two points as corners. If no other point is inside this rectangle, you own its diagonal, but you can't own two diagonals if the two rectangles overlap in a way that at least one corner of one is strictly inside the other. (Sharing a corner is OK! The somewhat ugly condition is necessary, as otherwise with two parallel diagonals of points, you can own O(n^2) diagonals.) Again, can you own between O(n) diagonals (the points lie on a diagonal) and O(n log n) (the points lie chaotic)?
I'm now sitting on my master thesis for almost two years, and like to namedrop an example that needs an "in-between" value, say O(n loglog n). Do you know one? (A reference would be even better.)
Disclaimer: The work is almost done, it's just for a insignificant subordinate clause, but it's driving me mad that any of the umphty wacky sequences I have come up with falls either into the maximum or minimum case. Also, it could come extremely handy for any follow-up work. If you can't come up with one off-hand, I drop the question altogether. After all, I already have written 150 pages... :-)