用于反转 log(n) 中的子数组的数据结构
Data structure for inverting a subarray in log(n)
构建具有函数的数据结构：
set(arr,n) - 用长度为 n 的数组 arr 初始化结构。时间 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 次反转，它就会搞砸。
下面是我们如何设计这样的数据结构。
事实上，使用平衡二叉搜索树是一个很好的开始。
首先，让我们将数组元素成对存储 (index, value)。
自然地，元素按索引排序，因此树的中序遍历将以其原始顺序生成数组。
现在，如果我们维护一个平衡的二叉搜索树，并在每个节点中存储子树的大小，我们已经可以在 O(log n) 中执行 fetch。
接下来，让我们只假装我们存储索引。
相反，我们仍然像处理 (index, value) 对一样排列元素，但只存储值。
index 现在被 隐式存储 并且可以按如下方式计算。
从根开始，向下到目标节点。
每当我们移动到左子树时，index 都不会改变。
移动到右子树时，将左子树的大小加一（当前顶点的大小）到 index.
此时我们得到的是一个定长数组，存储在平衡二叉搜索树中。访问（读取或写入）任何元素都需要 O(log n)，而不是普通固定长度数组的 O(1)，因此是时候从所有麻烦中获得一些好处了。
下一步是设计一种方法，在给定左侧部分所需大小的情况下，将我们的数组拆分为O(log n)中的左右部分，合并 两个数组串联。
这一步引入了对我们选择的平衡二叉搜索树的依赖。
Treap 是明显的候选者，因为它建立在 split 和 merge 基元之上，因此此改进是免费的。
也许也可以在 O(log n) 中拆分一个 Red-black tree or a Splay tree（尽管我承认我自己并没有试图弄清楚细节）。
现在，该结构已经比数组更强大：它允许在 O(log n) 中拆分和连接 "arrays"，尽管元素访问也和 O(log n) 一样慢。
请注意，如果我们此时仍显式存储 index，这是不可能的，因为索引会在 split 或 merge 的右侧被破坏操作。
终于到了介绍invert操作的时候了。
让我们在每个节点中存储一个标志，以指示是否必须反转该节点的整个子树。
这个标志将延迟传播：每当我们访问一个节点，在做任何事情之前，检查标志是否是true。
如果是这种情况，交换左右子树，toggle(true <-> false)两个子树的根节点中的flag，将当前节点中的flag设置为false.
现在，当我们想要反转子数组时：
- 通过两次split操作将数组分成三部分（子数组之前、子数组本身和子数组之后），
- toggle (
true <-> false) 中间（子数组）部分根部的flag，
- 然后通过两次 merge 操作将这三个部分合并回原来的顺序。
构建具有函数的数据结构：
set(arr,n) - 用长度为 n 的数组 arr 初始化结构。时间 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 次反转，它就会搞砸。
下面是我们如何设计这样的数据结构。 事实上，使用平衡二叉搜索树是一个很好的开始。
首先，让我们将数组元素成对存储 (index, value)。
自然地，元素按索引排序，因此树的中序遍历将以其原始顺序生成数组。
现在，如果我们维护一个平衡的二叉搜索树，并在每个节点中存储子树的大小，我们已经可以在 O(log n) 中执行 fetch。
接下来，让我们只假装我们存储索引。
相反，我们仍然像处理 (index, value) 对一样排列元素，但只存储值。
index 现在被 隐式存储 并且可以按如下方式计算。
从根开始，向下到目标节点。
每当我们移动到左子树时，index 都不会改变。
移动到右子树时，将左子树的大小加一（当前顶点的大小）到 index.
此时我们得到的是一个定长数组，存储在平衡二叉搜索树中。访问（读取或写入）任何元素都需要 O(log n)，而不是普通固定长度数组的 O(1)，因此是时候从所有麻烦中获得一些好处了。
下一步是设计一种方法，在给定左侧部分所需大小的情况下，将我们的数组拆分为O(log n)中的左右部分，合并 两个数组串联。
这一步引入了对我们选择的平衡二叉搜索树的依赖。
Treap 是明显的候选者，因为它建立在 split 和 merge 基元之上，因此此改进是免费的。
也许也可以在 O(log n) 中拆分一个 Red-black tree or a Splay tree（尽管我承认我自己并没有试图弄清楚细节）。
现在，该结构已经比数组更强大：它允许在 O(log n) 中拆分和连接 "arrays"，尽管元素访问也和 O(log n) 一样慢。
请注意，如果我们此时仍显式存储 index，这是不可能的，因为索引会在 split 或 merge 的右侧被破坏操作。
终于到了介绍invert操作的时候了。
让我们在每个节点中存储一个标志，以指示是否必须反转该节点的整个子树。
这个标志将延迟传播：每当我们访问一个节点，在做任何事情之前，检查标志是否是true。
如果是这种情况，交换左右子树，toggle(true <-> false)两个子树的根节点中的flag，将当前节点中的flag设置为false.
现在，当我们想要反转子数组时：
- 通过两次split操作将数组分成三部分（子数组之前、子数组本身和子数组之后），
- toggle (
true <-> false) 中间（子数组）部分根部的flag， - 然后通过两次 merge 操作将这三个部分合并回原来的顺序。