What progress has been made on persistent catenable deques in the last decade?
I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though.


I don't think there are any published simplifications since then. As far as I can tell, the T&amp;M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have slowed down in the last few years.
As far as adding splitting while maintaining constant-time concat, you can look at Brodal et al's "Purely Functional Worst Case Constant Time Catenable Sorted Lists" for some references. I don't think this problem is solved yet. As far as I know, the best known result is O(lg lg n) concat and O(lg min(n - i,i)) split, from Kaplan &amp; Tarjan's "Purely functional representations of catenable sorted lists". For the insertion and deletion case that involves lookup, see the lower bounds I mentioned in another question on ropes. For the insertion and deletion case without lookup, you can use an order-maintenance structure.