¿Qué estructura de datos almacenaría eficientemente los rangos de enteros?

Necesito mantener una colección de enteros en el rango de 0 a 65535 para poder hacer rápidamente lo siguiente:

• Insertar un nuevo entero
• Insertar un rango de enteros contiguos
• Eliminar un número entero
• Eliminar todos los enteros debajo de un entero
• Prueba si hay un número entero presente

Mis datos tienen la propiedad de que a menudo contienen corridas de enteros en la colección. Por ejemplo, la colección podría ser en algún momento:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

El enfoque más simple es usar un árbol binario equilibrado como el C ++ std :: set, sin embargo, al usar eso, no estoy aprovechando el hecho de que a menudo tengo series de números. ¿Quizás sería mejor almacenar una colección de gamas? Pero eso significa que un rango debe poder dividirse si se elimina un número entero en su medio, o unirse si se completa el espacio entre dos rangos.

¿Existen estructuras de datos existentes que sean adecuadas para este problema?

Le sugiero que use un árbol de búsqueda binario, aumentado para que las hojas puedan contener un intervalo (una serie de enteros consecutivos). Mantenga el invariante de que los intervalos no se superponen y están en orden (siguiendo el árbol de búsqueda invariante). (Esto puede considerarse un caso especial de un árbol de intervalos o un árbol de segmentos, para el caso especial donde los intervalos no se superponen).

Esta estructura de datos puede admitir todas sus operaciones en tiempo , donde es el número de intervalos. Como estamos garantizados , esperaría que esto sea bastante eficiente. (En particular, sí, puede dividir un intervalo en dos partes o fusionar dos intervalos adyacentes en un solo intervalo en tiempo ).n n ≤ 65535 O ( lg n $O(\lg n)$$n$$n\le 65535$$O(\lg n)$

En primer lugar, su pregunta está muy mal redactada, aunque no sea por otra razón, porque "rápidamente" no significa mucho. Deberá proporcionar alguna métrica de lo que significa "rápido".

Más allá de eso, cuando se trata de idear un diseño para un problema, primero debe comprender el problema muy bien y hacer muchas preguntas adicionales . Las preguntas relevantes en este caso parecerían ser (sin ningún orden en particular):

• ¿Todas estas operaciones deben ser igualmente rápidas o algunas son más importantes que otras?
• ¿Hay otras consideraciones?
• ¿Es la memoria una preocupación en absoluto?
• ¿Es preocupante la capacidad de realizar inserciones, eliminaciones y búsquedas desde múltiples hilos?
• ¿La carga de trabajo se centra principalmente en la inserción? Eliminando? ¿Buscando?

En segundo lugar, si su dominio del problema es realmente , esta discusión parece simplemente tonta. ¿Es realmente necesario un algoritmo elegante y elegante ? ¿Especialmente cuando una matriz simple es una excelente opción, que cubre las operaciones de un solo número entero en tiempo constante, las operaciones de rango en tiempo lineal y cuesta espacio lineal?$[0, 65535]$

Para un poco más de trabajo, podría ahorrar espacio si eso es una preocupación, a expensas de la velocidad al almacenar los datos como bits en enteros 8192. Aunque conceptualmente las operaciones de un solo número entero seguirían siendo tiempo constante y las operaciones de rango entero seguirían siendo tiempo lineal, serían más lentas.

Entonces, si este es realmente tu problema, diría que usa una matriz y continúa con otras cosas más importantes con el código.

Si este no es realmente su problema y hay otras consideraciones que no ha transmitido (por ejemplo, quizás el dominio no es realmente y estaba tratando de simplificar el problema sobre el que estaba preguntando), entonces necesitará para hacer su pregunta nuevamente, esta vez contándonos el problema real .$[0, 65535]$

Puede considerar una estructura de datos Integer , como un árbol Van Emde Boas . Una estructura de datos entera funciona en un universo fijo . Algunas de las operaciones que ha mencionado se pueden implementar de manera muy eficiente. En particular, la inserción, eliminación y solicitud de un solo elemento se ejecuta en . Las otras operaciones (inserción / eliminación masiva) pueden ser más costosas, sin embargo, usando bittricks en el árbol Van Emde Boas, debería poder acelerar por un factor de aproximadamente el tamaño de palabra de su sistema.O ( log log u $\mathcal{U}=\{0,\ldots,u-1\}$$O(\log \log u)$

Dependiendo de la estructura de sus datos, puede haber muchas alternativas inteligentes para almacenar sus datos.