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,

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.