I've written a Data Structure[1] for C++ to handle this problem. It uses counted B+Trees internally and is a drop in replacement for C++14's std::vector.

[1] https://github.com/det/segmented_tree