enigma algorítmica: secuencia con acceso aleatorio, la inserción y remoción

Question

Describe una estructura de datos donde:

• cualquier artículo es indexado por un valor integral como en una matriz
  • un número entero puede índice de una sola
  valor
  • enteros utilizados para elementos de índice son contiguas : que van de 1 a n sin agujeros
• conseguir el artículo en la posición i (es decir: el elemento asociado al número entero i) debe ser lo más rápido posible
  • de acceso aleatorio
• Inserción de un nuevo elemento en la posición i debe ser lo más rápido posible
  • esto le haga cambiar cualquier artículo de i en adelante
• Eliminar un elemento en la posición i también debería ser lo más rápido posible
  • esto izquierdo cambiar cualquier artículo de i+1 en adelante

EDIT: una pequeña cosa que me olvidé de : los índices de elementos solo se pueden desplazar al agregar/eliminar uno, no se pueden intercambiar aleatoriamente.

En esta descripción n es el tamaño de la estructura (es decir: el número de elementos que contiene), y i es un número entero genérico (1 < = i < = n), por supuesto.

---

Oí esto de un hombre que conocí en mi facultad. No sé si es una pregunta de entrevista, una pregunta de examen, solo un enigma o qué, pero supongo que podría ser todo.

Si no recuerdo mal (pero bueno, era antes de diciembre 24ª), dijo una estructura de datos podría ser implementado, ya sea con O(sqrt n) inserción/remoción y O(1) tiempo de acceso, o con O(log n) para cualquier operación.

---

EDITAR: Algunas respuestas correctas han sido dadas. Léelo si no quieres pensar más sobre este problema.

Answer 1

Bueno, cualquier tipo de árbol binario de autoequilibrado (por ejemplo, rojo-negro) proporcionará las tres operaciones para O(logn). C++ map RB mencionado es un ejemplo (si no me olvidé completamente de C++).

En cuanto a la operación de indexación (get), hay un truco estándar. Almacenaremos en cada nodo cuántos nodos tiene su subárbol izquierdo.Ahora podemos localizar el elemento en la posición i en O(logn) tiempo de una manera como esto

Data get(Node root, int i) { 
    if (i <= root.leftCount) { 
     return get(root.left, i); 
    } else if (i == root.leftCount + 1) { 
     return node; 
    } else { 
     return get(root.right, i - root.leftCount - 1); 
    } 
} 

Obviamente, se añade o elimina cada elemento de tiempo, leftCount valores tendrán que ser recalculado, pero que tendrá que ser hecho solamente para O(logn) nodos. (Piensa en cuántos nodos incluyen elimina uno en su subárbol izquierdo - sólo los directamente entre él y raíz)

Answer 2

Una lista de salto puede hacer operaciones de búsqueda de inserción/extracción/índice de cada uno en O(log n): http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

Para la inserción O(n^1/2)/eliminar y O(1) índice, supongo que algo así como un C++ deque, pero que consta de n^1/2 bloques contiguos, cada uno de n^1/2 elementos (+/- 1 en cada raíz cuadrada, por supuesto). Para eliminar, debe arrastrar hacia abajo parte del bloque que contiene el elemento eliminado (O(n^1/2)) y luego arrastrar hacia abajo entero de los bloques superiores, lo que haría ajustando un desplazamiento para cada bloque (como máximo O(n^1/2) bloques)) en lugar de mover realmente nada. Para insertar, puede que tenga que reasignar un bloque (O(n^1/2)) y ajustar las compensaciones. En ambos casos, también puede tener que desplazar uno o dos elementos desde el inicio/fin de algunos bloques hasta el final/inicio del bloque anterior/siguiente, nuevamente como máximo O(n^1/2) veces, para mantener un invariante que no difiera en dos bloques. tamaño en más de 1, a excepción de la última que se utiliza para compensar la holgura. Finalmente, a veces tienes que crear o destruir un bloque. La búsqueda es O(1) porque puede acceder a un bloque del elemento que está buscando con una sola división, luego consultar los desplazamientos almacenados para uno o dos bloques para encontrarlo realmente.

No sé cómo se llama, o si me perdí algunos detalles importantes que significa que no funciona como lo describí.