A string kept as a binary tree of short pieces: index by weights, concat with one new node, and split or edit the middle without copying the rest.
This interactive visualization needs JavaScript.