使用2-3树维护列表

(我要回答wrt。一棵红黑的树而不是2-3棵树,因为这更容易推理。这个答案需要稍作调整,以适应2-3棵树)

与其让每个顶点都在其左边存储元素的数量,不如让每个顶点在它作为根的子树中存储元素的数量。在树中从根向下导航时,请保持累计和 你左手边的元素。无论何时移动到顶点的右子对象 五 ,添加 五 的左子树到 s .

连接两个列表 和 B (也就是说, B 附加到 )只需创建一个新顶点 五 A B 它分别是左、右孩子。更新根目录的子树中的元素数 五 元素个数之和 和 B

将一个列表一分为二,只需移除要切掉的列表根的边。

但是,根据列表的大小,树可能会变得不平衡。在一定数量的“不平衡”连接或拆分之后,您必须重新平衡树。我必须承认,我不太清楚这件事的时间复杂性。我很确定你不能得到固定时间的摊销,但你可能可以得到O(logn)时间的摊销。