在Haskell库中是否存在类似数组的数据结构，即O(log n)插入和O(log n)检索?我能用拉链推导出一个吗?&

Question

我惊讶地发现，Array，例如，每当发生变化时，重建整个数据结构，花费O(n)。

我希望有人已经实现了一个纯拉链数组(或拉链向量)，有O(log n)查询和O(log n)插入。

这样的实现是否已经存在?我的搜索(Zipper Array和Zipper Vector)没有得到这样的库。

如果没有，是否有一种方法可以自动从已经存在的数组和/或向量中派生出一个拉链?

最坏的情况是，我可能会尝试自己构建一个，但我必须刷红黑树(看看拉链是否与它们一起工作!)

---

编辑:确实O(1)不会与树一起工作，正如注释中所指出的

Answer 1

手指树的插入和查询次数为O(log n)。