Finger trees are even more impressive than this (very clever) data structure. A sequence based on finger trees supports:

* O(lg n) lookup, split, concatenate, random insert/delete

* amortized O(1) push and pop at either end of the sequence

* Caching the value of a monoid reduction of each subsequence. Surprisingly useful.

Trellises are easier to understand, though.