There's a data structure called treap: that's a randomized binary search tree, which is also a heap on randomly generated so-called "priorities".
There's a variation of this structure, where keys are implicit, they aren't stored in the tree, but we consider the ordered index of the node in the tree as this node's key. We need to store size of subtree in each node instead of key. This technique enables us to think about treap like some kind of array, which supports lots of operation in O(log N) time: insertion, deletion, reversion of subarray, changing on interval and so on.
I know a bit about this structure, but no so much. I tried to google it, but I've found only lots of articles about treap itself, but nothing about this "implicit treap" / "indexed list". I even don't know its name, because my native language isn't English and lecture I've listened used the native term of structure, not English original term. This native term can be directly translated in English as "Treap on the implicit keys" or "Cartesian tree on the implicit keys".
Can anybody point me at the article about this structure or tell me its original name? Thank you.
P.S. Sorry if my English wasn't understandable enough.
UPD: Some extra explanation about structure I'm looking for.
Consider a usual treap with randomly chosen priorities and keys, which are actual user data stored in the tree. Then let's imagine we have some other user info stored in every node, and keys are nothing but the search keys. Next step is calculating and maintaining the subtree size in each node: we have to update this parameter after every Merge/Split/Add/Remove, but it allows us to find, for example, Kth element of the tree in O(log N) time.
When we have subtree sizes in each node, we can throw keys away and imagine that treap represents an array of user data in inorder traversal. Array index of each element can be easily calculated from subtree s