树堆隐式钥匙 [英] Treap with implicit keys
问题描述
有所谓树堆的数据结构：这是一个随机二叉搜索树，这也是对随机产生所谓的优先级堆
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".
有这样的结构，其中键是隐式的，它们不是存储在树中的变化，但我们认为在树作为此节点的密钥的节点的有序索引。我们需要存储子树的大小在每个节点，而不是关键。这项技术使我们思考树堆像某种阵列，它支持很多操作在为O（log n）时间：插入，删除，子阵逆转，改变区间等等
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。很抱歉，如果我的英语还不够理解的。
P.S. Sorry if my English wasn't understandable enough.
UPD：关于结构我在寻找一些额外的解释
UPD: Some extra explanation about structure I'm looking for.
考虑具有随机选择的优先级和键，它们是存储在树中实际的用户数据通常的树堆。然后让我们想象一下，我们有存储在每个节点的一些其他用户信息和密钥都不过是搜索键。下一步骤是计算并保持的子树尺寸中的每个节点：我们必须更新后该参数每隔合并/分流/添加/删除，但它使我们能够找到，例如，为O树的第K个元件（日志N）时间。
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.
当我们有树的大小在每个节点上，我们可以抛出键程，想象树堆重新presents用户数据中序遍历数组。每个元素的数组索引可以从子树尺寸很容易地计算出来。现在，我们可以添加/数组的中间删除一个元素或分割该数组 - 都在为O（log n）时间
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 sizes. Now we can add/remove an element in the middle of array or split this array - all in O(log N) time.
我们也可以使多重操作 - 例如，一个恒定的值添加到我们的阵列的所有元素。要实现这一点，我们必须使这种操作延迟，在重$ P $的每个节点添加参数psents延迟常数，它必须是后加入到这一节点的子阵中的所有元素，而推的变化必要时升转降。加上常数到子阵列或绘画（标志）的子阵列可延迟以这种方式，作为扭转子阵列（这里在比特节点子阵列必须被倒延迟信息），等等。
We can also make "multiple" operation - for example, add a constant value to all elements of our "array". To implement this, we have to make this operation delayed, add a parameter in every node that represents a delayed constant which has to be "later" added to all the elements of this node's subarray, and "push" the changes up to down as necessary. Adding a constant to subarray or painting (marking) the subarray can be made delayed in this way, as reversing the subarray (here the delayed info in the node in the bit "subarray has to be reversed"), and so on.
UPD2：下面是 code段 - 片的少量的信息，我发现。没有注意到西里尔:)词снеявнымключом的意思直接翻译与隐含的关键。
UPD2: Here's code snippet - piece of the small amount of information I've found. Don't notice cyrillic :) Words "с неявным ключом" mean in direct translation "with implicit key".
推荐答案
您可以通过逆转（第7页，第3.1节）排序符号排列找到的文件由卡普兰和Verbin这个数据结构： http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf 。
You can find this data structure in the paper by Kaplan and Verbin on sorting signed permutations by reversals (page 7, section 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.
这篇关于树堆隐式钥匙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
