This is a paper that I've been meaning to read: Finger trees: a simple general-purpose data structure. It introduces a data structure to represent sequences. The data structure allows constant-time access to both ends of the sequence and logarithmic-time concatenation and splitting.