What progress has been made on persistent catenable deques in the last decade?

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:

1. 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?

2. Has anyone come up with any simplifications since then?

3. 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?

• Are you asking us to do your research for you? Have you used Google Scholar or similar? Some engines even offer "cited by" searches, so it should be easy to find the newest work, assuming they do cite the "classics". Question 1. looks salvageable, if you made the question mostly about that fact (explanation needed). (Note that proper references should include title, authors and year at least, and an "unbreakable" link using DOI or such.)
– Raphael
Mar 25, 2014 at 0:36