实际上是，支持合并的纯函数式deque。这个翻译是deepl给出的。
大家都知道单链表是可以简单可持久化的，但是双链表不行。大家都会用单链表均摊地实现双端队列。那么如何可持久化双端队列呢?今天小编就带大家来看一看 https://dl.acm.org/doi/pdf/10.1145/324133.324139 这篇论文。
这个可持久化deque是严格$O(1)$，而不是均摊$O(1)$。
这里面有很多很有趣的技巧。
不支持合并的严格可持久化双端队列
Clancy-Knuth表示法
用来表示一个数，并且在$\pm 1$的时候变化量是严格$O(1)$。
我们允许一个二进制数中出现$2$，这称为redundant binary representation，这样的东西简称为数。显然一个数值对应的数一般不唯一。
定义一个数是好的，当且仅当忽略掉所有$1$之后，不存在两个相邻的$2$，并且最低的非$1$位不是$2$。
我们在对好数做$+1$的时候，由于最低的非$1$位不是$2$，所以可以直接$+1$，但是这可能让它变得不好。我们找到最低的非$1$位，如果它是$0$则啥事没有，否则我们把这一位置为$0$，把下一位增加$1$。这样变化量就是严格$O(1)$。
我们用满二叉树来索引元素。定义一个级别为$k$的buffer是不超过$5$棵高度为$k$的满二叉树的集合，我们将这样的树称为 元素。一个deque由一个三元组表示 : 前缀buffer，后缀buffer，和剥掉这两个buffer之后的deque，这个deque称为它的儿子。一个deque和它的儿子和它的儿子的儿子……统称为它的子deque，根据语境直接简称为deque。
现在两个简单的操作就是，我们可以把$k$层的一个元素拆成两个元素扔到$k-1$层，也可以把$k-1$层的两个元素合并起来扔到$k$层。所以这个就是某种很redundant的二进制表示。使用类似于刚才的Clancy-Knuth表示法的方法，称一个buffer是红色(对应于2)的，当且仅当它有$0$或$5$个元素，黄色(1)是$1,4$，绿色(0)是$2,3$。定义一个deque的颜色是它前后buffer颜色中更危险的或者说更大的那个，特别地，如果最后一层的deque的buffer之一是空的，我们定义它的颜色是它非空buffer的颜色。
定义一个deque是semiregular的，当且仅当把它和所有儿子的颜色拿出来排成一排(它自己排在第一个)，把所有黄色忽略掉之后，不存在相邻的两个红色。定义一个deque是regular的，当且仅当它是semiregular的，并且这个序列中第一个黄色之外的颜色是绿色。如果一个deque是regular的，那么它的顶层必然不是红色，所以我们可以直接在顶层加/删点来做到$O(1)$。
在一次操作之后，regular的性质可能被破坏。我们还是找到最浅的红/绿deque，如果它是绿色，那么啥事没有。如果它是红色，我们就希望调整一下。
第一个问题是如何找到最浅的红/绿deque。我们把这些点表示成若干条链，每条链是一个红/绿deque和它后面跟着的极长黄点，然后这些链之间再用一个单链表串起来。接下来可以看到，一次操作最多访问前三条链，并且最多访问每条链的前两个点，而它带来的链划分的变化是容易处理的。
我们描述一个方法把任意semiregular的deque调整为regular的deque。考虑设这个deque里最浅的红deque是$i$，它的儿子是$i+1$，$p_i,p_{i+1}$是它们的前缀buffer，$s_i,s_{i+1}$是后缀buffer。
$i+1$不可能是红的。如果$i+1$是最后一层，它的buffer可能有一个是空的，否则$p_{i+1},s_{i+1}$都不可能是空的，因为semiregular的deque里面没有两个红deque相邻。
接下来有以下两种情况 :
-
如果$i+1$层的buffer总大小$\geq 2$，或者$i+1$层的buffer总大小$\leq 1$并且$i$层的至少一个buffer大小$\geq 2$。如果$i$层的一个buffer大小$\geq 4$，从它里面拿两个接起来移动到$i+1$层，由于$i+1$层不是红的，这必然可行。如果$i$层的一个buffer大小$\leq 1$，从$i+1$层拆一个移动到它。如果此时$i+1$层空了，删掉它。此时$i$必然是绿色。
-
如果$i+1$层的buffer总大小$\leq 1$，并且$i$层的两个buffer大小都$\leq 1$。此时我们把这些元素拆出来，最多有三个$i$级的元素，爆力重构即可。
但是我们一直没说怎么随机访问!注意到如果知道这个数在哪个buffer里，因为buffer是满二叉树，通过维护左右端点，我们可以$O(1)$地找到它。问题是要$O(1)$地找在哪个buffer，注意到buffer只有$O(\log n)$个，且每次操作变化量严格$O(1)$，所以直接$\log$大小分块预处理即可。
支持合并
未完成，可能不会去完成了。
我们不再使用一条祖孙链，而是使用二叉树。定义一个triple是一个三元组，它包括前缀buffer，后缀buffer和子deque。前后缀buffer都是一个不需要支持合并的deque，除此之外我们提到deque都是正在描述的支持合并的deque。定义一个deque是一个或两个triple。
如果一个deque是一个triple，这个triple称为only triple，要求它的前后缀buffer各有至少五个元素，或者其中一个和子deque是空的，另一个只要非空就行。如果一个deque是两个triple，它们分别称为left triple和right triple，left triple要求前缀buffer有至少五个元素，而后缀有恰好两个，right triple反过来。
定义一个triple是一个stored triple，当且仅当前后缀buffer各有至少三个元素，或者其中一个和子deque是空的，另一个有至少三个元素。定义一个triple是一个only triple，当且仅当前后缀buffer各有至少五个元素，或者其中一个和子deque是空的，另一个只要非空就行。定义一个triple是一个，right triple反过来。
接下来给triple分配颜色。我们增加一种橙色，介于红黄之间。
-
stored triple和叶子triple总是绿色的。
-
对于非叶left triple，如果它的前缀buffer包含$\geq 8,=7,=6,=5$个元素，它是绿，黄，橙，红色的。right triple是对称的。
-
对于非叶only triple，按照前后buffer大小的$\min$，与left triple一样分配颜色。
刚才提到了这些triple构成二叉树。我们为黄色或橙色的triple定义一个重儿子，黄色的triple的重儿子是它的左儿子，橙色的是它的右儿子。重儿子定义了一个链剖分，每条链从一个黄/橙triple出发，经过若干个黄/橙triple，直到一个红/绿triple结束(叶子都是绿色)。定义一条链的颜色是它的链尾的颜色。
定义一个deque是semiregular的，当且仅当从红triple的儿子开始的链都是绿色的，并且从橙triple的轻儿子(如果有)开始的链都是绿色的。定义一个deque是regular的，当且仅当它是semiregular的，并且从根(可能有两个)开始的链都是绿色的。
为了快速找到链尾，对于每个链头我们维护它的链尾。定义一个deque的compressed forest为把每个链尾的父边断开，转而连到链头得到的森林。
接下来我们考虑操作。
引理1 往任何一个点的前/后buffer push一个元素，不会影响deque的semiregular和regular的性质。
证明 如果这个点的颜色没变，那么啥事没有。如果变了，那么必然是红变橙，橙变黄，黄变绿之一。
-
对于黄变绿，显然不可能出问题。
-
对于橙变黄，只有父亲是红色，并且这个点有两个儿子，此时重儿子发生切换，才有可能出问题。由于原deque是semiregular的，这个点原来的轻儿子的重链是绿色的，所以切换后它的重链还是绿色的，所以没有问题。
-
对于红变橙，原deque只可能是semiregular的。两个儿子的重链都是绿色的，所以没有问题。
考虑合并，假设我们要合并$d_1,d_2$。很复杂。
-
如果两个deque根的所有buffer都是非空的。我们直接把这俩都搞成一个根的，然后接在一起形成一个有两个根的deque就行了。只考虑$d_1$，$d_2$是一样的。
-
如果$d_1$由两个triple组成。
- 如果第一个triple不是叶子。
-