构建数据结构以在poly-logn时间执行反向和报告查询

Question

给定n个数的序列,{ a ₁,a ₂,a ₃,...,a _n }.构建数据结构,以便在poly-logn时间内执行以下操作.

1. 反转(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. 报告(i):

   报告我个元素的顺序,即一个_我.

这里,poly-logn表示log n的一些幂.像log(n)·log(n)可能是可以接受的.

[ 注意:感谢Baswana教授提出这个问题.]

Answer 1

我正在考虑使用二叉树，其中一个节点用“左|右”指示符以及该子树中的元素数量进行扩充。

• 如果指示器设置为Left先读取左孩子，然后读取右孩子
• 否则（设置为Right）则首先读取右孩子，然后读取左孩子

这Report是相当明显的：O(log n)

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

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

• 反转包含该序列的最小子树（指示符的变化）
• 将Revert运算应用于[a..i-1]和[j+1..b]

但不确定它是否真的有效：/

编辑：

以前的解决方案不起作用:)我无法想象一个不重新排列树的解决方案，并且它们不尊重复杂性要求。

我会把它留在那里，以防它给其他人一些想法，然后我会删除它，除非我自己找到解决方案。