Choose a sequence representation by the operation that must be cheap. Each representation still has a boundary condition and a cost that a happy-path lookup can hide.
Lessons
- Gap buffers: pay when the edit cursor crosses text
- Ropes: share text chunks across immutable revisions
- Unrolled lists: link small blocks instead of single items
- Segmented arrays: locate blocks through cumulative lengths