Preprocese una matriz para contar un elemento en un segmento (¿reducción a RMQ?)

Dada una matriz de números naturales , donde es una constante, quiero responder en consultas de la forma: "¿cuántas veces aparece en la matriz entre los índices y "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

La matriz debe ser preprocesada en tiempo lineal. En particular, me gustaría saber si hay una reducción en la consulta mínima de rango.

Esto es equivalente a RMQ en el caso donde y desea consultar el número de unidades dentro de un intervalo. Así que podemos usar es . ^{No pude responder mi propia pregunta debido a los límites de SE.} $k=1$

algorithms arrays algorithm-design andy
fuente

Puede reducir la distinción de elementos a su problema (en tiempo lineal). Tal vez hablar de un modelo está en orden?

Aryabhata

@Aryabhata, ¿cuál es exactamente el problema de distinción de elementos? Ahora estoy leyendo esto: en.wikipedia.org/wiki/Range_Queries

andy

Esto es mucho más fácil que RMQ. Sugerencia: Debido a que k es una constante, el preprocesamiento puede pasar un tiempo proporcional a kn y aún cuenta como tiempo lineal.

Tsuyoshi Ito

@Aryabhata: La reducción de la que creo que estás hablando no funciona porque k es una constante en este problema.

Tsuyoshi Ito

Por si acaso, si la matriz se proporciona al principio y no se actualiza después, RMQ es una exageración, como sugerí en mi comentario anterior.

Tsuyoshi Ito

Respuestas:

Como es constante, podemos almacenar el recuento de cada elemento en el rango para en en tiempo y espacio. La observación principal es que puede hacer una matriz bidimensional en tiempo , luego consultar rangos al encontrar la diferencia en los índices en tiempo constante. $k$ $0..m$ $0\leq m \lt n$ $0..n$ $O(nk) = O(n)$ count[pos][elem] = occurences of 'elem' in the indices 0..pos $O(nk)$ $i,j$

Preprocesamiento

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

Consulta

(asume que i, j son ambos límites inclusivos)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

Si la matriz también se actualiza durante todo el proceso de consulta, puede usar árboles Fenwick (índice binario) en lugar de la matriz. Esto le permite actualizar en y consultar en . $k$ count $O(\log n)$ $O(\log n)$

Disculpas por cualquier problema con esta respuesta, es mi primera.

Goldy
fuente