Vectors are cheap to implement because they map naturally to the Random Access Memory model. Vector's element access or update is very fast, it has O(1) complexity with low hidden constants. But insertions and deletions are slow, they require O(N) time to complete. There is no solution for dynamic vector problem that provides both access and insertion/deletion with O(1) time complexity.

It is possible to create dynamic vector using Partial Sum Tree with O(log N) worst time complexity for both access and insertion/deletion. That is acceptable for use cases when ultra-fast access is not necessary.

Let us have a sequence of N values, split it to blocks of limited length. The sequence of block lengths is delta sequence for the sequence of block offsets. Partial Sum Tree can be used to find a block given its offset in O(log N) time as it is shown on the following figure.

If we need to find an element with index 9 (S9), we need to perform the following operations on the Partial Sum Tree build over blocks of the sequence:

1. find a block with max offset less than 9: block_num = findLT(9);
2. find the requested element's position in the block: element_offset = 9 - sum(0, block_num);

All operations take O(log N) time.

If we need to insert an element into the sequence, we need:

1. find the block and position in the block to insert into using the algorithm described above;
2. insert element into the block, this operation takes O(1) time because block size is limited;
3. find the path from target block to the root of the tree;
4. increase all values in the path by 1.
5. if target block is full, then split it first, adding new entry to partial sum tree. Split tree's entry if necessary.

Deletion is performed the same way.

The closes analog of such data structure is Rope. Unlike Rope that uses binary search tree, Dynamic Vector uses balanced multiary search tree.