Prétraiter un tableau pour compter un élément dans une tranche (réduction en RMQ?)

Étant donné un tableau de nombres naturels , où est une constante, je veux répondre dans les requêtes de la forme: «combien de fois apparaît-il dans le tableau entre les indices et "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

Le tableau doit être prétraité en temps linéaire. En particulier, j'aimerais savoir s'il y a une réduction de l'intervalle minimum de requête.

Cela équivaut à RMQ dans le cas où et que vous souhaitez interroger le nombre de uns dans un intervalle. Nous pouvons donc utiliser ce . ^{Je n'ai pas pu répondre à ma propre question à cause des limites de SE.} $k=1$

algorithms arrays algorithm-design Andy
la source

Vous pouvez réduire la distinction des éléments à votre problème (en temps linéaire). Peut-être que parler d'un modèle est de mise?

Aryabhata

@Aryabhata quel est exactement le problème de distinction des éléments? Maintenant je lis ceci: en.wikipedia.org/wiki/Range_Queries

andy

C'est beaucoup plus facile que RMQ. Astuce: Parce que k est une constante, le prétraitement peut passer du temps proportionnel à kn et il compte toujours comme du temps linéaire.

Tsuyoshi Ito

@Aryabhata: La réduction dont je pense que vous parlez ne fonctionne pas car k est une constante dans ce problème.

Tsuyoshi Ito

Juste au cas où, si le tableau est donné au début et n'est pas mis à jour par la suite, RMQ est une exagération, comme je l'ai suggéré dans mon commentaire précédent.

Tsuyoshi Ito

Réponses:

$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étraitement

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

Requete

(suppose que i, j sont des bornes inclusives)

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

$k$ count $O(\log n)$ $O(\log n)$

Toutes mes excuses pour tout problème avec cette réponse, c'est ma première.

Goldy
la source