Zero-based array implementation with logarithmic insertion time
All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL.

In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a rope, which is a stronger kind of string (see Wikipedia). Ropes are designed for exactly this purpose.