indexing - Implementation of a data structure with O(logn) access and O(logn) insertion? -

indexing - Implementation of a data structure with O(logn) access and O(logn) insertion? -

does know of info construction can access , delete k-th item in worst case o(logn) , supports operation of inserting item after k-th item in worst case o(logn)?

yes. describe can achieved augmented tree. every node has counter indicating number of nodes in subtree (including itself). leaf nodes, counter 1. root node, counter total number of nodes. way, can find k-th item binary search starting @ root. whenever insert/remove element, have update counters in path goes position root.

this kind of trees have been called order statistic trees, rank trees, counter trees...

you can find implementation here , 1 here.

see chapter 14, "augmenting info structures" in great book "intorduction algorithms", cormen, leiserson, rivest , stein.

data-structures indexing insertion random-access