Conclusion de l'introduction

L'ensemble Python peut gérer un ensemble, mais comme il n'a pas d'index dans l'élément, l'opération "sortir le xème élément du plus petit" ne peut être effectuée qu'avec $ O (N) $ pour le nombre d'éléments N. ne pas.

Ah, c'est trop tard.

En conclusion, l'arbre indexé binaire et la dichotomie donnent $ O ((logN) ^ 2) $. Je ne sais pas si cela peut être fait plus rapidement.

(4.13 post-scriptum)

Merci d'avoir signalé M. Salmonize et M. Joe. Bien qu'il s'agisse de $ O ((logN) ^ 2) $, en appliquant la dichotomie sur BIT, la partie dichotomie n'a pas besoin du traitement de requête de BIT, et elle est accélérée à $ O (logN) $.

Quel genre de raison?

Préparez un arbre indexé binaire (BIT). Quoi? Je ne sais pas BIT? https://ja.wikipedia.org/wiki/フェニック木

Lors de l'ajout de x à l'ensemble, disons que nous ajoutons +1 au xème élément de BIT. Par exemple, je veux créer un ensemble de {3, 1, 4}! Si vous pensez

+1 au troisième élément du tableau BIT +1 au premier élément du tableau BIT +1 au 4ème élément du tableau BIT

C'est acceptable.

Considérons maintenant lower_bound. Recherchez deux minutes. Lorsque vous voulez le xème élément du plus petit

Une dichotomie utilisant le jugement "Y a-t-il x ou plus d'éléments inférieurs ou égaux à y?" Trouve le nombre d'éléments inférieurs ou égaux à y dans $ O (logN) $ dans BIT.

De plus, puisque la dichotomie elle-même coûte $ O (logN) $

Le total est $ O ((logN) ^ 2) $. Je vois.

Contrainte

Si vous voulez gérer des flottants et des strs, vous devez concevoir. S'il s'agit d'un flottant, vous pouvez multiplier le nombre d'origine par un nombre constant, et str peut utiliser le code de caractère, mais cela n'a pas l'air pratique.

Il peut également être vulnérable aux requêtes en ligne car il n'est pas aussi puissant que vous pourriez le penser pour les changements dynamiques. Même lors du stockage d'un grand nombre, cela ne fonctionnera que si la compression des coordonnées est effectuée.

Conclusion

Eh bien, c'est plus rapide que de penser à un ensemble ordinal avec ensemble ... L'arbre de recherche de bisection d'équilibre semble plus pratique (fin)

Chaque article a une fin

Au fait, je n'ai pas écrit le code.