I am surprised to find that Array, for example, rebuilds the whole data structure whenever a change occurs, taking O(n).

I'd expect someone to have already implemented a Zipper Array (or zipper vector) that is pure and has O(log n) queries and O(log n) insert.

Does such implementation already exist? My searches (for Zipper Array and Zipper Vector) yielded no such library.

If not, is there a way to automatically derive a zipper from the already existent array and or vector?

Worst case scenario, I might try to build one myself, but I'd have to brush up on red black trees (and see if zippers work well with them!)

EDIT: Indeed O(1) would not work with trees, as noted in comments

CodePudding user response：

Finger trees have O(log n) insert and query.