在log（n）中反转子阵列的数据结构 [英] Data structure for inverting a subarray in log(n)

问题描述

构建具有以下功能的数据结构：

Build a Data structure that has functions:

set（arr，n） strong> - 使用长度 n 的数组 arr 初始化结构。时间 O（n）

set(arr,n) - initialize the structure with array arr of length n. Time O(n)

fetch（i） - 抓取 arr [i] 。时间 O（log（n））

invert（k，j ） - （当 0 <= k <= j <= n ）反转子数组 [k，j] 。意思是 [4,7,2,8,5,4] 与 invert（2,5）成为 [4,7,4,5,8,2] 。时间 O（log（n））

invert(k,j) - (when 0 <= k <= j <= n) inverts the sub-array [k,j]. meaning [4,7,2,8,5,4] with invert(2,5) becomes [4,7,4,5,8,2]. Time O(log(n))

如何在二叉搜索树中保存索引并使用标记指数倒数？但是如果我做了一个以上的反转，那就搞砸了。

How about saving the indices in binary search tree and using a flag saying the index is inverted? But if I do more than 1 invert, it mess it up.

推荐答案

下面是我们如何设计这样一个数据结构。
事实上，使用平衡二叉搜索树是一个好主意。

Here is how we can approach designing such a data structure. Indeed, using a balanced binary search tree is a good idea to start.

首先，我们将数组元素存储为对（ index，value）。
当然这些元素是按索引排序的，所以按顺序遍历一棵树将以原始顺序生成数组。

First, let us store array elements as pairs (index, value). Naturally, the elements are sorted by index, so that the in-order traversal of a tree will yield the array in its original order.

现在，如果我们维护一个平衡的二叉搜索树，并将子树的大小存储在每个节点中，我们可以在 O（log n）中执行 fetch

Now, if we maintain a balanced binary search tree, and store the size of the subtree in each node, we can already do fetch in O(log n).

接下来，让我们只假装我们存储索引。
相反，我们仍然像我们在（index，value）对中一样排列元素，但只存储该值。
索引现在隐藏，可以计算如下。
从根目录开始，到目标节点。
每当我们移动到左子树时，索引不会更改。
移动到右子树时，将左子树的大小加上一个（当前顶点的大小）添加到索引。

Next, let us only pretend we store the index. Instead, we still arrange elements as we did with (index, value) pairs, but store only the value. The index is now stored implicitly and can be calculated as follows. Start from the root and go down to the target node. Whenever we move to a left subtree, the index does not change. When moving to a right subtree, add the size of the left subtree plus one (the size of the current vertex) to the index.

我们现在得到的是一个固定长度的数组，它存储在一个平衡的二叉搜索树中。 O（log n）访问（读取或写入）任何元素，而不是 O（1）对于一个简单的固定长度的数组，所以它是大概时间为所有的麻烦获得一些好处。

What we got at this point is a fixed-length array stored in a balanced binary search tree. It takes O(log n) to access (read or write) any element, as opposed to O(1) for a plain fixed-length array, so it is about time to get some benefit for all the trouble.

下一步是设计一种方法来 split 我们的数组在 O（log n）中的左侧和右侧部分，给定左侧所需的大小，合并两个数组通过连接。
这一步介绍了对平衡二叉搜索树的选择的依赖。
Treap 是明显的候选人，因为它建立在分裂之上和合并原语，所以这种改进是免费的。
也许也可以拆分红黑树或 O（log n） Splay tree $ c>（虽然我承认我没有尝试自己弄清楚细节）。

The next step is to devise a way to split our array into left and right parts in O(log n) given the required size of the left part, and merge two arrays by concatenation. This step introduces dependency on our choice of the balanced binary search tree. Treap is the obvious candidate since it is built on top of the split and merge primitives, so this improvement comes for free. Perhaps it is also possible to split a Red-black tree or a Splay tree in O(log n) (though I admit I didn't try to figure out the details myself).

现在，结构已经比数组更强大了：它允许尽管元素访问与 O（log n） O（log n）中分割和连接数组 c>也
请注意，如果我们仍然在这一点上明确地存储 index 这是不可能的，因为索引会在拆分的右侧部分/ strong>或合并操作。

Right now, the structure is already more powerful than an array: it allows splitting and concatenation of "arrays" in O(log n), although element access is as slow as O(log n) too. Note that this would not be possible if we still stored index explicitly at this point, since indices would be broken in the right part of a split or merge operation.

最后，现在是介绍反转操作的时候了。
让我们在每个节点中存储一个标志来表示这个节点的整个子树是否必须被反转。
这个标志将会悄悄传播：每当我们访问一个节点，在做任何事情之前，检查标志是否是 true 。
如果是这种情况，请交换左和右子树，切换（ true< - > false ）两个子树的根节点，并将当前节点中的标志设置为 false 。

Finally, it is time to introduce the invert operation. Let us store a flag in each node to signal whether the whole subtree of this node has to be inverted. This flag will be lazily propagating: whenever we access a node, before doing anything, check if the flag is true. If this is the case, swap the left and right subtrees, toggle (true <-> false) the flag in the root nodes of both subtrees, and set the flag in the current node to false.

现在，当我们要反转一个子阵列：

Now, when we want to invert a subarray:

• 将数组分成三部分（子阵列之前，子阵列本身和子阵列之后）由两个分割操作


• 切换（ true< - > false ）中间（子阵列）部分的根中的标志


• 然后通过两个合并操作将原来的三个部分合并回来。

• split the array into three parts (before the subarray, the subarray itself, and after the subarray) by two split operations,
• toggle (true <-> false) the flag in the root of the middle (subarray) part,
• then merge the three parts back in their original order by two merge operations.

这篇关于在log（n）中反转子阵列的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！