algorithm - 用于反转 log(n) 中的子数组的数据结构

Question

构建一个具有函数的数据结构:

set(arr,n) - 用数组 arr 初始化结构长度n .时间 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))

如何将索引保存在二叉搜索树中并使用表示索引已倒置的标志？但是，如果我进行超过 1 次反转，它就会搞砸。

Answer 1

下面是我们如何设计这样一个数据结构。 事实上，使用平衡二叉搜索树是一个不错的开始。

首先，让我们将数组元素成对存储 (index, value) . 自然地，元素按索引排序，因此树的中序遍历将以其原始顺序生成数组。

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

接下来，让我们只假装我们存储索引。 相反，我们仍然像处理 (index, value) 那样排列元素。对，但只存储值。 index现在被隐式存储并且可以按如下方式计算。 从根开始，向下到目标节点。 每当我们移动到左子树时，index没有改变。 移动到右子树时，将左子树的大小加一(当前顶点的大小)到index。 .

此时我们得到的是一个定长数组，存储在平衡二叉搜索树中。需要O(log n)访问(读取或写入)任何元素，而不是 O(1)对于一个普通的固定长度数组，所以是时候为所有的麻烦获得一些好处了。

下一步是设计一种方法，将我们的数组拆分成O(log n) 中的左右两部分。给定左侧部分所需的大小，并通过串联合并两个数组。 这一步引入了对我们选择的平衡二叉搜索树的依赖。 Treap是明显的候选者，因为它建立在 split 和 merge 原语之上，所以这种改进是免费的。 也许也可以拆分一个 Red-black tree或 Splay tree在 O(log n) (尽管我承认我自己并没有试图弄清楚细节)。

现在，该结构已经比数组更强大:它允许拆分和连接 O(log n) 中的“数组” ，尽管元素访问速度与 O(log n) 一样慢也。 请注意，如果我们仍然存储 index，这是不可能的。明确在这一点上，因为索引将在 split 或 merge 操作的右侧被破坏。

最后，是时候介绍invert操作了。 让我们在每个节点中存储一个标志，以指示是否必须反转该节点的整个子树。 这个标志将延迟传播:每当我们访问一个节点，在做任何事情之前，检查标志是否是true。 . 如果是这种情况，交换左右子树，切换(true <-> false)两个子树的根节点中的标志，并将当前节点中的标志设置为false。 .

现在，当我们想要反转子数组时:

• 通过两次拆分操作将数组分成三部分(子数组之前、子数组本身和子数组之后)，
• 切换 ( true <-> false ) 中间(子数组)部分根部的标志，
• 然后通过两次合并操作将这三个部分合并回原来的顺序。