Pré-processe uma matriz para contar um elemento em uma fatia (redução para RMQ?)

Dado um array de números naturais , onde é uma constante, eu quero responder em consultas da forma: "quantas vezes é que aparecer na matriz entre os índices e "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

A matriz deve ser pré-processada em tempo linear. Em particular, gostaria de saber se há uma redução no intervalo de consulta mínima.

Isso é equivalente a RMQ no caso em que $k=1$ e você deseja consultar o número de unidades em um intervalo. Para que possamos usá- lo .
^{Não pude responder minha própria pergunta por causa dos limites da SE.}

algorithms arrays algorithm-design andy
fonte

Você pode reduzir a distinção do elemento ao seu problema (em tempo linear). Talvez falar sobre um modelo esteja em ordem?

Aryabhata

@Aryabhata, o que é exatamente o problema de distinção entre elementos? Agora estou lendo o seguinte: en.wikipedia.org/wiki/Range_Queries

andy

Isso é muito mais fácil que o RMQ. Dica: Como k é uma constante, o pré-processamento pode passar um tempo proporcional a kn e ainda conta como tempo linear.

Tsuyoshi Ito

@Aryabhata: A redução que eu acho que você está falando não funciona porque k é uma constante nesse problema.

Tsuyoshi Ito

Apenas no caso, se a matriz for fornecida no início e não for atualizada posteriormente, o RMQ será um exagero, como sugeri no meu comentário anterior.

Tsuyoshi Ito

Respostas:

Como é constante, podemos armazenar a contagem de cada elemento no intervalo para em em tempo e espaço. A observação principal é que você pode criar uma matriz bidimensional em tempo , em seguida, consultar intervalos encontrando a diferença nos índices em tempo 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$

Pré-processando

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]] ++

Inquerir

(assume que i, j são ambos limites inclusivos)

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

Se a matriz também estiver sendo atualizada durante o processo de consulta, você poderá usar as árvores Fenwick (índice binário) no lugar da matriz. Isso permite que você atualize em e consulte em . $k$ count $O(\log n)$ $O(\log n)$

Desculpas por quaisquer problemas com esta resposta, é o meu primeiro.

Goldy
fonte