Considere el siguiente problema:
Deje ser una constante. Se nos da una matriz -ary de y 's. Deje .
Queremos crear una estructura de datos preprocesando para realizar el siguiente tipo de operaciones de consulta:
- Dadas las coordenadas de un -ary caja , ¿hay un en la caja?
- Dadas las coordenadas de un cuadro -ary , devuelve la posición de un en el cuadro (si hay uno).
Las operaciones deben realizarse en tiempo constante . La complejidad del tiempo se mide en una máquina RAM. El tiempo y el espacio de preprocesamiento para la estructura de datos no son importantes para nosotros.
La pregunta es ¿cuánto espacio (en complejidad de bits) necesitamos para almacenar una estructura de datos que permita las operaciones anteriores?
El límite inferior trivial es bits, ya que la matriz se puede reconstruir para estas consultas (por lo que la estructura de datos debe tener al menos la misma cantidad de información).
El límite superior trivial es almacenar la respuesta a todas las consultas. Eso necesitaría bits. Sin embargo, sospechamos que esto se puede hacer de manera mucho más eficiente.
Por ejemplo, considere el caso especial donde . En este caso, podemos usar una estructura de datos RMQ sucinta para resolver el primer problema, y la estructura de datos requiere bits para almacenar.
¿Cuál es una estructura de datos eficiente para esta tarea?
¿Qué tan bajo puede ser la complejidad del espacio (el número de bits) para soportar estas operaciones (o solo la primera operación)?
Actualización (1/15): en el caso especial , usar bits es suficiente (en realidad mejor, , donde es el número de 's en ) reduciendo el problema a un problema predecesor y utilizando la reducción del problema predecesor a un diccionario completamente indexable (FID). Consulte " Más prisa, menos desperdicio: reducir la redundancia en diccionarios completamente indexables " por Grossi, Orlandi, Raman y Rao (2009).
Actualización (27/06): Nuevamente, reduzca el problema a RMQ. Utilizamos un RMQ dimensional de Yuan y Atallah para obtener un límite superior en la cantidad de espacio requerido cuando es fijo.
Respuestas:
Puede ahorrar mucho más en memoria si solo permite la complejidad del tiempo logarítmico. Puede implementar un árbol de segmentos kD que necesitará una memoria N * 2 ^ k bits, y se ejecuta en complejidad de tiempo logarítmica para ambas subtareas y complejidad de tiempo lineal para construir el árbol.
Si quiere estrictamente O (1), precalcule todo.
fuente