Créer une structure de données en O (n + k) temps qui peut me permettre de trouver le nombre d'entiers dans une certaine gamme dans le tableau en temps constant

Question

J'ai un tableau d'entiers et je connais la gamme de valeurs de ces entiers

Je veux créer une structure de données en temps O (n + k) qui peut me permettre de trouver le nombre d'entiers dans une certaine plage dans le tableau en temps constant.

Est-ce possible, je ne veux pas trier le tableau, est-ce possible avec une sorte d'arbre équilibré? Arbres AVL?

Answer 1

Vous pouvez créer un autre tableau dans lequel les valeurs correspondent au nombre de valeurs dans le tableau cible supérieur à l'index. Ensuite, pour trouver le nombre dans la plage, il vous suffit de trouver un [max] - un [min].

Pour créer la matrice, vous pouvez parcourir le tableau cible en incrémentant la valeur à l'index du tableau de recherche (O (n)). Ensuite, vous parcourez le tableau de recherche à l'envers, en faisant de chaque valeur la somme de lui-même et toutes les valeurs qui la suivent dans le tableau (O (k), si k est la plage des données). Bien sûr, cela nécessiterait un peu de mémoire, en fonction de la taille de votre tableau, mais il aurait les caractéristiques de performance dont vous avez besoin.

Answer 2

opérations d'arbres sont habituellement log (n)

I aurait un tableau de la taille de la plage qui je pré-remplir avec « nombre d'entiers inférieure à cette valeur » et retrouver différence entre le mini et maxi de portée demandée. c'est le temps de const.