Count will still be possible to implement in O(h) time.

Implement 2 operations: 1) Count number of elements less than x 2) Count number of elements less than or equal to x.

Both are just "split+get size of left(+merge back)"

Okay, so how exactly would you define split operation if both left and right subtrees can contain the same value? I understand that the tree will still be balanced because of random priority, but I'm not convinced how you will implement count in this structure.

    10
   /  \
  9    10
   \    \
   10    20
         /
        10

I'm not really sure what problem is.

So I need to split tree to one that contains numbers =x.

Suppose for a second, that I replaced all numbers x with x + epsilon * i where i is its number in order (so that its still a search tree) and epsilon is small. We can split this, right? But not a single comparison changed because I only care =x.

Same with <= and > (you may need subtracting)

You may also check implementation (edited out of one of nearby comments) which will do first split correctly (didn't need second one) but it's easy with copy and paste.

You are however modifying the values in treap explicitly here. This is exactly what I claimed. You can modify the usual treap implementation like this or you can keep a frequency variable at every node. Without these modifications, all operations cannot be done in logarithmic time when there can be duplicates.

No, I don't modify them. I say suppose I changed

Okay, I think we are trying to imply the same thing. Suppose you changed, then I agree it is possible. But if you do not change, its not possible (unless you keep a frequency variable). Can we agree with each other now?

I don't think we imply the same thing.(more like opposite things)

Anyway, I think discussion is in dead end, so we'd probably should stop it

PS: implementation is available in nearby comment

Treap can easily answer a query "How many integers are there in range [a,b)?". You just hold count in every node like you would do for treap with implicit key. Then to get answer you split by a, then the rest by b and get count from the middle tree. Then merge everything back together. Getting frequency of x is same as asking number of integers in [x,x+1).

And split still works in the usual way. Let's assume we split node into trees with values < x and >=x . We arrive to some node. If it has value other than x, we do the usual. If it has value x, we know, that right subtree is definitely >=x since it has elements greater than or probably some equal to x. Thus root with its right subtree is the right tree for answer and we should split left subtree. Still works in O(height).

Note, that adding 1 will only work with integers, but it's still easy to overcome

knightL Just to confirm, so if we allow equal elements in both left and right subtrees, we can do the split as you defined above? Do you have an implementation of Treap written by you or anyone else?

Yes, we can. I prefer the implementation from e-maxx . There is also riadwaw's implementation in second revision of this comment with some fancy C++11 stuff :) . All the usual treap methods are in private section.

Jeez, it did not really seem to me that this can be done with treap, without any sort of modifications. It seems I have a different insert implementation which caused all the confusion. Sorry for the inconvenience, please ignore my other comments regarding this issue. And thanks for clearing it up.

Strange. I was sure, that there could be a problem with balancing since priorities don't actually define the tree structure. If all keys are different and all priorities are different, only one treap can be built. With same keys we may have any tree we like. Probably randomness still help in some way after all.

OK, I have one more stupid doubt. How do we allow equal elements into both left and right subtrees? While inserting a value X, we split it into 2 treaps L( < X) and R( >  = X).

Now while merging X and R, we need to check priorities, and according to that an element will go into the left or right subtree of R right?

X will either be root (if has highest priority) or will go to left subtree of R

Cool, thanks!