Haskell 库中是否有类似数组的数据结构，插入时间复杂度为 O(log n)，检索时间复杂度为 O(log n)？我可以用拉链衍生一个吗？

Question

例如，我惊讶地发现Array，只要发生更改，就会重建整个数据结构，时间复杂度为 O(n)。

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

这样的实施已经存在吗？我的搜索（拉链数组和拉链矢量）没有找到这样的库。

如果没有，有没有办法从已经存在的数组和/或向量中自动导出拉链？

最坏的情况是，我可能会尝试自己建造一棵，但我必须温习一下红黑树（看看拉链是否适合它们！）

---

编辑：确实 O(1) 不适用于树，如评论中所述

Answer 1

手指树的插入和查询时间复杂度为 O(log n)。