I'm interested in persistent catenable deques: deques that can be concatenated.
Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (see Okasaki for references). Then a couple years later, Kaplan, Okasaki, and Tarjan came up with a simpler implementation using more general mutation in a disciplined manner. Then in 2003, Mihaesau and Tarjan came up with a simpler, non-bootstrapped strictly functional version.
My questions:
The Mihaesau and Tarjan catenable deques appear, to my untrained eye, to offer $O(\log n)$, or possibly even $O(\log(\min(i, n-i)))$ random access (lookup and modify). Is this correct?
Has anyone come up with any simplifications since then?
Has anyone either found a way to combine $O(\log n)$ (or, better yet, $O(\log(\min(i,n-i)))$) splitting along with $O(1)$ concatenation, or proved that it can't be done? For that matter, what about $O(\log n)$ arbitrary insertion and/or deletion?