Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time.
For a specific problem I was musing about a balanced tree that would allow for an zero-based array implementation with logarithmic time for all of the following operations: insertion, removal and finding the next and previous element.
I'm reasonably sure it should be straight-forward to implement: The non-leaf nodes would have to store the count of elements in their left branch respectively.
Such a data structure should be useful in text editors, as the user obviously can insert text anywhere in the document and yet the editor is supposed to render a screenfull of text around a given location quickly as well.
My question: What's this data structure called? Is there a buzzword I can google? (Such as "B-tree", "red-black tree", etc. for key-ordered search trees?)