在多项式对数时间内构建数据结构以执行反向查询和报告查询

Question

给定一个长度为n的数列{a1,a2,a3,…,an}，构建一种数据结构，使得以下操作可以在poly-logn时间内完成。

1. Reverse(i,j):

反转区间i到j中所有元素，如下所示： 原始序列： <… a[i-1], a[i], a[i+1], …, a[j-1], a[j], a[j+1], …> 交换后的序列： <… a[i-1], a[j], a[j-1], …, a[i+1], a[i], a[j+1], …> 2. Report(i):

报告第i个元素在序列中的位置，即a[i]。

这里，poly-logn指log n的某个幂次，如log(n)·log(n)可能是可接受的。

[注：感谢Baswana教授提出此问题。]

- ramshankar

---

这是一道作业题吗？这是一个很棒的问题，但如果它是为了课堂而设定的，你真的应该让我们知道并描述一下你已经尝试过什么。 - templatetypedef

@templatetypedef：这不是作业问题。这个问题是Baswana教授在上学期为有动力的学生提出的（感谢他），在这里讨论是完全可以的。 - ramshankar

注意：polylog(n) ~~ log(n)**k for some k。 - Matthieu M.

将所有元素放入高度平衡的二叉树中。增加一个名为RANK的字段，即当执行reverse(i,j)查询时，RANK(v)=以v为根的子树的孩子数+1，从i到j沿着路径到根的节点被标记为“反转”。无论如何，我正在回答问题，但尚未完成。 - ramshankar

跳表能解决这个问题吗？ - Lasse V. Karlsen

使用隐式Treap（也称为隐式笛卡尔树）。在Google上搜索代码。 - mrk

Answer 1

我在考虑使用二叉树，其中节点增加了一个左|右指示器和此子树中元素的数量。

• 如果指示器设置为Left，则从左侧开始读取子节点，然后读取右侧子节点
• 否则（设置为Right），则从右侧开始读取子节点，然后读取左侧子节点

Report相当明显：O(log n)

Revert稍微复杂一些，我不确定它是否真正有效。

想法是“隔离”要在特定子树中反转的元素序列（最低可能）。该子树包含范围[a..b]，包括[i..j]

• 反转包含此序列的最小子树（更改指示器）
• 对[a..i-1]和[j+1..b]应用Revert操作

不确定它是否真正有效 :/

编辑：

之前的解决方案不起作用 :) 我无法想象一个不重新排列树并且不符合复杂度要求的解决方案。

我会把这个留在这里，以防它能给其他人一些启示，除非我自己找到解决方案，否则我会在之后删除它。

- Matthieu M.

---

有些范围并不完全在同一个根节点下...比如说如果你有8个节点..那么3-6将是一个范围，其中一半在一边，另一半在另一边。 - Yochai Timmer

@Yochai：不过，总会有一个共同的根源，那是变革的起点。 - Matthieu M.

当然有一个共同的根节点，但我的意思是，尽管它们有一个共同的根节点，你不能在那里保存“翻转”信息，因为一半的节点在树的一侧，另一半在另一侧。以我的例子为例，如果你翻转了3-6，那么1-2和7-8就是正常顺序，但3-6的唯一共同根节点是根节点。 - Yochai Timmer

@Yochai: 啊，是的，正如我所说，我不确定它是否有效，而当我吃饱后，我意识到它并没有。这确实是一个有趣的谜题，没有我知道的数据结构（足够）似乎能够适应它:D - Matthieu M.

Answer 2

Splay树+您的装饰可以得到O(log n)摊销。 Matthieu遇到的结构问题是由于我们可以在O(log n)摊销时间内将根更改为任何节点而解决的。

（注：此数据结构是旅行推销员问题的本地搜索算法的重要组成部分，人们发现具有高阶数的两层和三层树在实践中更有效。）

- user613073